Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.
Conjecture Let be an eulerian graph of minimum degree , and let be an eulerian tour of . Then admits a decomposition into cycles none of which contains two consecutive edges of .
Kotzig proved the converse statement:
Theorem Let be an eulerian graph of minimum degree and let be a decomposition into cycles of . Then admits an eulerian tour such that none of the , , contains two consecutive edges of .
For more details on eulerian graphs, see [F].
Bibliography
*[F] H. Fleischner. Eulerian Graphs and Related Topics. Part 1. Vol. 1. Annals of Discrete Mathematics, Vol. 45, (1990) North-Holland, Amsterdam.
* indicates original appearance(s) of problem.