G-94-02
Elementary Proof of the Cycle-Plus-Triangles Theorem
BibTeX reference
Let G be a graph which has a Hamilton circuit H such that if the edges of H are deleted then the rest decomposes into disjoint triangles. The cycle-plus-triangles theorem says that G is 3-chromatic. This was conjectured by P. Erdös in 1987 and proved by H. Fleischner and M. Stiebitz in a non-elementary way in 1991. In this paper, an elementary proof is given for a slightly stronger proposition.
Published February 1994 , 15 pages