![](/files/happy5.png)
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
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 4 $](/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png)
![$ W $](/files/tex/48948390b5dc5ab9a52c0afaff3e950050be14a2.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ W $](/files/tex/48948390b5dc5ab9a52c0afaff3e950050be14a2.png)
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
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 4 $](/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png)
![$ (C_1, \dots , C_p) $](/files/tex/6025c50de3316308c2908ba0f0b94725e93151ca.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C_i $](/files/tex/366ed51c03af1594b11b42173acfc750beb64886.png)
![$ 1\leq i\leq p $](/files/tex/4e9f329cd88669519e011cd4cd2fb9a90b5b4828.png)
![$ W $](/files/tex/48948390b5dc5ab9a52c0afaff3e950050be14a2.png)
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.