{"id":"arxiv/2607.13225","url":"https://arxiv.org/abs/2607.13225","tags":["math.CO"],"score":0,"title":"Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture","domain":"math.CO","source":"arxiv","authors":["Nikolay Ulyanov"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-14","reactions":{}}