Groupe d’études et de recherche en analyse des décisions


Elementary Proof of the Cycle-Plus-Triangles Theorem

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