Let α denote the average degree, and δ denote the minimum degree of a graph. An edge is light if both its endpoints have degree bounded by a constant depending only on α and δ. A graph is degree-constrained if α<2δ. The primary result of this paper is that every degree-constrained graph has a light edge. Most previous results in this direction have been for embedded graphs. This result is extended in a variety of ways. First it is proved that there exists a constant c(α,δ) such that for every 0≤<c(α,δ), every degree-constrained graph with n vertices has at least ε·n light edges. An analogous result is proved guaranteeing a matching of light edges. The method is refined in the case of planar graphs to obtain improved degree bounds.

, ,
Discrete Mathematics
Computational Geometry Lab

Bose, P, Smid, M, & Wood, D. (2004). Light edges in degree-constrained graphs. Discrete Mathematics, 282(1-3), 35–41. doi:10.1016/j.disc.2003.12.003