Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture
Abstract
We prove Sabidussi's compatibility conjecture. Let G be a finite connected multigraph in which every vertex has even degree and the minimum degree is at least four, and let T be an Euler tour of G. The edges of G can be partitioned into circuits (connected $2$-regular subgraphs) so that no circuit contains two edges used consecutively anywhere in T. In fact, the edges can be four-coloured so that every such pair receives different colours and every colour class has even degree at every vertex. We use a counting argument based on the Chevalley-Warning theorem to show that a four-colouring with the required properties exists. Splitting each colour class into circuits then gives the desired compatible decomposition. Formalization in Lean 4 is also available in the author's github.
Related
- Unique Normal Forms: Proof-Graph Counterexamples, Infinite-Carrier Certificates, and Confluence Repair
- A proof of the Stanley-Stembridge conjecture
- A streamlined proof of the Kakeya set conjecture in R3
- A proof of Alexander’s Conjecture on an Inequality of Cassels
- A Proof of Ebenfelt's weak SOS Conjecture
BibTeX
@misc{ulyanov2026graph,
title = {{Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture}},
author = {Nikolay Ulyanov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.13225},
eprint = {2607.13225},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.13225},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture
AU - Nikolay Ulyanov
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2607.13225
UR - https://arxiv.org/abs/2607.13225
AB - We prove Sabidussi's compatibility conjecture. Let G be a finite connected multigraph in which every vertex has even degree and the minimum degree is at least four, and let T be an Euler tour of G. The edges of G can be partitioned into circuits (connected $2$-regular subgraphs) so that no circuit contains two edges used consecutively anywhere in T. In fact, the edges can be four-coloured so that every such pair receives different colours and every colour class has even degree at every vertex. We use a counting argument based on the Chevalley-Warning theorem to show that a four-colouring with the required properties exists. Splitting each colour class into circuits then gives the desired compatible decomposition. Formalization in Lean 4 is also available in the author's github.
ER -