Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.

OPG_eulerian_cycle_decomposition_avoiding_tour_transitions

Source: Open Problem Garden: decomposing_an_eulerian_graph_into_cycles_with_no_two_consecutives_edges_on_a_prescirbed_eulerian_tour

Medium ★★ Graph Theory » Basic Graph Theory » Cycles

Author: Sabidussi, Gert— posted by fhavet on 2013-03-04

Status open medium confidence

Sabidussi's conjecture — that every Eulerian graph of minimum degree $4$ admits a cycle decomposition compatible with any prescribed Eulerian tour (no two consecutive tour-edges in the same cycle) — remains open in full generality. Known pre-2013 partial results include the case of planar graphs (Fleischner) and $K_5$-minor-free graphs (Fan and Zhang, 2000); a weak version for $80$-edge-connected graphs was also established. No verifiable post-2013 resolution of the general conjecture was found.

Reviewer notes. All known partial results (Fleischner for planar graphs; Fan–Zhang 2000 for K₅-minor-free graphs; compatible decomposition for 80-edge-connected graphs) predate the 2013 OPG posting and thus are not listed in since_posted. A Google Scholar AI summary claimed a 2024 Graphs-and-Combinatorics paper ('Perfect Pseudo-Matchings in Cubic Graphs', Fleischner, Gh, Klocker, doi:10.1007/s00373-024-02844-y) concludes that Sabidussi's Compatibility Conjecture is false, but this claim could not be verified: Springer required authentication, no arXiv preprint was found, and a direct Google Scholar description of the same paper contained no mention of Sabidussi's conjecture — strongly suggesting the earlier summary was a hallucination. The AJC volume 58 (February 2014) PDF 'A cycle decomposition conjecture for Eulerian graphs' was also inaccessible (binary PDF, content unreadable). Status is therefore reported as open with medium confidence.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 03) (web search enabled).

Conjecture. Let $ G $ be an eulerian graph of minimum degree $ 4 $ , and let $ W $ be an eulerian tour of $ G $ . Then $ G $ admits a decomposition into cycles none of which contains two consecutive edges of $ W $ .

Discussion

Kotzig proved the converse statement: Theorem Let $ G $ be an eulerian graph of minimum degree $ 4 $ and let $ (C_1, \dots , C_p) $ be a decomposition into cycles of $ G $ . Then $ G $ admits an eulerian tour such that none of the $ C_i $ , $ 1\leq i\leq p $ , contains two consecutive edges of $ W $ . 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.