# Compatible Euler-tours

If *G* is an undirected graph with even degrees then call two closed Eulerian walks **compatible** if no pair of incident edges occurs consecutively in both. Is it true that the maximum number of pairwise compatible Euler walks in an Eulerian graph of minimum degree *2d* is either *2d-2* or *2d-1*?

## Remarks

This conjecture appeared in ^{[1]}. Note that the upper bound *2d-1* is easy. It was motivated by an old result of Kotzig ^{[2]} which implies it is
true when *d=2*, and Jackson ^{[3]} gave a good characterization of connected 4-regular graphs that have 3 pairwise compatible Euler walks. Bouchet ^{[4]} gave a more general, defect version of this theorem.

Kotzig had previously conjectured that the upper bound is attained by [math]K_{2d+1}[/math], and this has been verified for arbitrary *d* in ^{[1]}. In ^{[5]} the conjecture was also verified when *d=3*. For more information and
references, see ^{[6]}.

## Related conjectures

## References

- ↑
^{1.0}^{1.1}B. Jackson,*Compatible Euler tours for transition systems in Eulerian graphs,*Discrete Math., 66 (1987) 127-131. DOI link. - ↑ A. Kotzig,
*Moves without forbidden transitions in a graph*, EUDML link - ↑ B. Jackson,
*A characterisation of graphs having three pairwise compatible Euler tours*, DOI link - ↑ A. Bouchet,
*Compatible Euler Tours and Supplementary Eulerian Vectors*, DOI link - ↑ B. Jackson, N. Wormald,
*Cycles containing matchings and pairwise compatible Euler tours,*J. Graph Theory 14 (1990), 127-138. DOI link. - ↑ B. Jackson,
*On circuit covers, circuit decompositions and Euler tours of graphs,*in Surveys in Combinatorics, 1993, K Walker ed., Cambridge University Press, (1993) 191-210. Google Books link.