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.

Graph, Light edge, Matching
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