On the Number of Disjoint Edges in a Graph
- 1 January 1963
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 15, 106-111
- https://doi.org/10.4153/cjm-1963-012-2
Abstract
In what follows we prove that a finite graph of n nodes in which each node has degree ≥ 1 but ≤ possesses a set of at least n/(1 + ) pairwise disjoint edges. Our principal theorem states an analogue of this result for the case when each node has degree ≥2: we show that in this case the graph possesses a set of at least 2n/(2 + max(4, )) mutually disjoint edges.Keywords
This publication has 1 reference indexed in Scilit:
- Map Colour Theorems Related To the Heawood Colour FormulaJournal of the London Mathematical Society, 1956