Back

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.

, 15 pages