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.
Paru en février 1994 , 15 pages