Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.13225
curl -X POST /api/v1/records/arxiv/2607.13225/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.13225/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'