A Counterexample to Wormald's Conjecture
We give a counterexample to Wormald's conjecture. A 16-vertex cubic graph, the disjoint union of $K_{3,3}$ with a 10-vertex bridged graph built from two subdivided copies of $K_4$, has no partition of its edges into two isomorphic spanning linear forests. The obstruction is parity: any such partition would force every monochromatic component to have even order while requiring a five-vertex side of a bridge to be partitioned into such components. Adjoining copies of $K_4$ gives counterexamples in every order $16+4t$. The counterexample is disconnected and leaves the connected case unresolved.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.00086
curl -X POST /api/v1/records/arxiv/2610.00086/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.00086/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'