DOIAbstract
AbstractLet α 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
Add to ORKG