On the structure of k -chromatic graphs
Gabriel Andrew Dirac · Mathematical Proceedings of the Cambridge Philosophical Society · 1967
Abstract It is shown that for k ≥ 5 in every k -chromatic graph there is a set of k distinct vertices V 1 , …, V k with the property that for i, j = 1, …, k and i ≠ j the graph contains the union of a set of 4 paths connecting V i and V j no two of which have any edge or any vertex besides V i and V j in common and k − 1 paths connecting V i and V j no two of which have any edge in common.