Cut every graph into half as many paths as vertices— Gallai's conjecture
Take any connected graph on n vertices. Gallai conjectured that its edges can always be split into at most ⌈n/2⌉ paths, each edge used exactly once. Sixty years on it is proved for a growing list of classes and verified by computer for small graphs, and open in general. This dossier is the machine-checked part: what we verified, the reductions we proved, the exact census of the graphs that need every path the bound allows, and one new lower bound that turned out to explain all of them.
The Problem
A path decomposition of a graph G is a set of paths whose edge sets partition E(G): every edge lies on exactly one path, and no path repeats a vertex. The path number p(G) is the smallest size of such a decomposition.
The bound cannot be improved. If every vertex of G has odd degree then every vertex must be an endpoint of some path — a path meets each of its interior vertices in two edges — so with n endpoints available and two per path, at least n/2 paths are needed. Every graph with all degrees odd is therefore tight, and there are many.
Computing p(G) is NP-hard, for a reason worth keeping in mind: p(G) = 1 exactly when G has a Hamiltonian path. So no polynomial-time formula can equal the path number unless P = NP — a constraint that shapes §6.
What Is Known
The conjecture is proved for many classes, and the proofs almost all attack the same object: the subgraph induced by the even-degree vertices, written GE. That is where the difficulty concentrates, because odd-degree vertices are forced to be path endpoints and therefore pay for themselves.
- Lovász (1968) — every graph on n vertices decomposes into at most ⌊n/2⌋ paths and cycles. This is the foundation everything else stands on, and it settles the conjecture outright when all degrees are odd.
- Pyber — holds when GE is a forest. Fan — holds when each block of GE is triangle-free with maximum degree at most three.
- Bonamy–Perrett (2019) — holds for maximum degree at most 5. Botler–Jiménez–Sambinelli–Wakabayashi — treewidth at most 3 (and later work at treewidth 4). Blanché–Bonamy–Bonichon — planar graphs. Also known for 2-degenerate graphs, block graphs, and Cartesian products.
- Verified by computer for all graphs on at most 11 vertices — Botler, Cunha and Sambinelli (2019), via an integer-programming model for the path number, together with bipartite graphs to 16 vertices and regular graphs to 14.
- The sharpened open question (Bonamy–Perrett). Can every connected graph be decomposed into at most ⌊n/2⌋ paths unless G is an odd semi-clique — a clique on 2k+1 vertices minus at most k−1 edges? At odd n, ⌊n/2⌋ = B(n) − 1, so this asks precisely which graphs are tight. Known for treewidth ≤ 3 and for planar graphs, where K₃ and K₅ minus an edge are the only exceptions.
The Verified Ledger
Everything in this section is a finite computation with certificates. Unlabeled graphs come from nauty's geng; each claimed decomposition is re-checked edge by edge; each claimed impossibility is an exhaustive search that terminated, and searches that hit their node budget are reported as undecided rather than counted on either side.
At n = 11 the population is A001349(11) = 1,006,700,565 connected graphs. Because 11 is odd, every graph with a vertex of degree at most 2 follows unconditionally from the verified 10-vertex case — see §4 — which leaves only the graphs of minimum degree 3. Those were checked in 15.5 minutes across 14 shards, with coverage asserted against an independent geng -u count so that no shard could silently drop work. The greedy engine sufficed for every single graph: zero escalations to the exhaustive solver, so nothing rests on a search that ran out of budget.
To guard against a coding error hiding inside the 42.7% that the reduction skips, the prescribed certificate was built and verified for 100,049 sampled degree-≤2 graphs at n = 11, deliberately spread across edge counts 10 through 47.
The Reduction Toolkit
These are the levers the campaign proved for itself. Two of them are unconditional reductions; the rest confine where the difficulty can hide. All are elementary, and all are very likely folklore — no priority is claimed.
Let G be connected with a vertex v of degree 2 whose neighbours u, w are non-adjacent, and set H = (G − v) + uw. Then H is a simple connected graph on n−1 vertices and p(G) ≤ p(H).
Proof. H is simple because uw ∉ E(G), and connected because any G-path through v enters and leaves by u–v–w, which the new edge short-circuits. Take any path decomposition of H. The edge uw lies on exactly one path P = A–u–w–B; replace P by A–u–v–w–B. Since v ∉ V(H) this is again a path, and the edges it covers are those of P with uw traded for uv and vw. The result covers E(H) ∖ {uw} ∪ {uv, vw} = E(G), each edge once, with the same number of paths. ∎
Being size-preserving is what makes it useful at even n, where B(n−1) = B(n) leaves no room to spend a path. It is also the one reduction here that stands alone, with no leftover hypothesis — and it is what made the 11-vertex sweep affordable.
Honest scope. If u and w are adjacent — v sits in a triangle — the substitution uncovers uw and the argument fails. For odd n the two edges at v already form the path u–v–w, so p(G) ≤ p(G−v) + 1 = B(n) suffices. For even n it suffices that some decomposition of G−v of size ≤ B(n) has u and w as ends of two distinct paths; distinctness matters, since appending v to both ends of a single u…w path closes a cycle. That held in all 7,328 instances arising at n ≤ 9, decided by exhaustive search.
Write E(G, v) for: G has a decomposition of size ≤ B(n) in which v is an end of some path. Three one-line arguments confine its failures.
A (splitting). If p(G) ≤ B(n) − 1 then E(G, v) holds for every v of positive degree: take such a decomposition; if no path ends at v, then v is interior to some path, and cutting that path at v yields two paths — one more part, still within B(n), and v now an end.
B (parity). In every decomposition, the number of paths ending at v is congruent to deg(v) mod 2 — each path uses two edges at v when v is interior and one when v is an end. So odd-degree vertices are ends for free.
G (orbit). E transfers along automorphisms, so every vertex-transitive graph satisfies it at every vertex — in particular every complete graph.
Together: E(G, v) can fail only if G is tight and deg(v) is even. Hence it holds for every graph with all degrees odd and for every tree. E was verified exhaustively for every connected graph and every vertex at n ≤ 9 — 2,719,830 certificates, zero failures.
G connected with a leaf x at a, H = G − x. If p(H) ≤ B(n−1) and E(H, a) holds then p(G) ≤ B(n): either H has slack and the edge ax becomes its own path, or H is tight and E(H, a) hands us a path ending at a to extend. Both parities, no search.
But it is an equivalence, not a shortcut.For tight H of odd order, E(H, a) holds exactly when p(H + a pendant at a) ≤ B(m+1) — so “E on order n−1” and “Gallai for leafy graphs of order n” are the same statement. Theorem D reorganises and localises the problem; it does not reduce it to anything easier, and we said so once we noticed.
Write cH(v, t) for the fewest paths in a decomposition of H having at least t paths ending at v, so cH(v, 0) = p(H). If v is a cut vertex splitting G into G₁ and G₂, sharing only v, then
Proof. (≤) Take decompositions attaining each cost, pick t paths ending at v on either side, pair them and concatenate at v — the sides share only v, so each concatenation is a path, and the result covers E(G) with |D₁| + |D₂| − t parts. (≥) In any decomposition of G, let s count the paths using edges of both sides. Such a path passes through v, and being a path it visits v exactly once, so it splits into exactly two pieces, each ending at v; every other path lies wholly on one side. So |D| = |D₁| + |D₂| − s with at least s paths ending at v on each side. ∎
Corollary. If the endpoint property holds on both pieces then t = 1 gives p(G) ≤ ⌈n₁/2⌉ + ⌈n₂/2⌉ − 1 ≤ ⌈n/2⌉. So with the degree-2 splice, a minimal counterexample to Gallai must be 2-connected with minimum degree 3 — unless E fails on one of its pieces. Verified exhaustively: the formula is exact on all 71,464 connected graphs with a cut vertex on ≤ 9 vertices, and in every one of them E held on both pieces, with the glued decomposition constructed and verified edge by edge.
Unlike the leaf reduction this is notcircular — G₁ and G₂ are strictly smaller — though “a minimal counterexample is 2-connected” is standard-issue reasoning in this area and is not claimed as new.
Deciding impossibility is what costs, so two exact prunes carry the censuses in §5.
Capacity. With r paths left to cover `rem` residual edges and no path able to hold more than n−1 edges, every path of any completing decomposition carries at least rem − (r−1)(n−1) edges, because the others absorb at most (r−1)(n−1) between them. Shorter candidates cannot appear in any solution.
End-count.When rem > (r−1)(n−1), all r remaining paths must be used, so they supply exactly 2r path-ends. A vertex of residual degree d hosts f of them with 2·(interior visits) + f = d and (d+f)/2 ≤ r, so f ≤ min(d, 2r−d). If those caps cannot sum to 2r, or one vertex is forced above its own cap, the branch is dead.
The effect is not marginal: thirteen graphs at 10 vertices had each survived 400,000,000 search nodes without a verdict, and the end-count prune refuted all thirteen at the root, in zero nodes. That is the difference between an exact census and one with an asterisk.
Which Graphs Are Tight
A graph is tight when it needs every path the bound allows. Tightness splits in two: lower-bound-forced, where one of the three classical bounds already reaches B(n), and structure-forced, where all three are strictly below B(n) and the graph is tight anyway. The second kind is the interesting kind, and it had never been counted at 10 vertices — deciding it means refuting a 4-path decomposition for each of 11.7 million graphs.
| n | connected | tight | lower-bound-forced | structure-forced |
|---|---|---|---|---|
| 6 | 112 | 47 | 44 | 3 |
| 8 | 11,117 | 1,284 | 1,233 | 51 |
| 10 | 11,716,571 | 307,266 | 305,585 | 1,681 |
The 10-vertex row is exact and complete: 11,409,305 graphs certified into ≤ 4 paths plus 307,266 tight sums to A001349(10) = 11,716,571 with nothing undecided. Two independent pipelines reach 1,681 by different routes, and the 305,585 reproduces an earlier streaming count from a different engine.
At odd order the picture is completely different — tight graphs are rare, and they are exactly the dense ones:
| n (odd) | connected | tight | tight graphs are… |
|---|---|---|---|
| 3 | 2 | 1 | K₃ |
| 5 | 21 | 2 | K₅, K₅ − e |
| 7 | 853 | 4 | K₇ minus ≤ 2 edges |
| 9 | 261,080 | 9 | K₉ minus ≤ 3 edges |
| 11 | 1,006,700,565 | 20 | K₁₁ minus ≤ 4 edges |
Those are exactly the odd semi-cliques, so this table is the Bonamy–Perrett question confirmed on a range — exhaustively for n ≤ 9, and at n = 11 for every graph with at least 45 edges, which is the hard region. Sparser bands at n = 11 are not claimed.
A New Lower Bound
Here is the one piece of this dossier we think is genuinely new, and it came from asking a simple question: are the structure-forced tight graphs really unexplained, or merely unexplained by global bounds? All three classical bounds count over the whole graph. So we looked for local ones.
Fix a decomposition into k paths and a vertex set S. Each path P meets S in some number cP of subpaths, covering |V(P) ∩ S| − cP edges inside S. Summing gives e(S) ≤ k·|S| − ΣcP, and three bounds fall out — density (a path is a forest, so this is Nash-Williams arboricity), local parity, and both at once. All three are valid, and sharper than the classical maximum on some graphs. They explained 43 of the 1,681 structure-forced graphs at 10 vertices. Counting was not the answer.
What the counting bounds miss is visible in the two smallest unexplained graphs. One is a triangle joined by an edge to a vertex carrying two leaves; the other is two triangles joined by a bridge. A triangle needs two paths on its own, and only a limited number of paths can enter it across a small boundary. That is not a density statement — it is about a cut.
Proof. Fix a decomposition into k paths. The subpaths lying inside S form a path decomposition of G[S], so there are at least p(G[S]) of them, contributing at least 2·p(G[S]) subpath-ends. Each such end is either a genuine end of one of the k paths, lying in S, or a point where a path steps out of S along one of the b boundary edges — and each boundary edge, being used by exactly one path, provides at most one exit. Writing ES for the number of path-ends inside S, this gives 2·p(G[S]) ≤ ES + b. Independently, parity forces ES ≥ oddS, since every odd-degree vertex ends at least one path. The identical argument applies to V∖S with the same b, and the 2k ends of the decomposition split between the two sides: 2k = ES + EV∖S. ∎
Taking S = ∅ recovers the classical odd-vertex bound, so this is a genuine generalisation rather than an unrelated inequality. It is also the only bound here that sees a cut, and unlike the others it is recursive — it calls the path number of induced subgraphs.
The result: it explains all of them.
| n | structure-forced tight | explained by counting (L1–L3) | explained by the boundary bound | left unexplained |
|---|---|---|---|---|
| 6 | 3 | 1 | 3 | 0 |
| 8 | 51 | 8 | 51 | 0 |
| 10 | 1,681 | 43 | 1,681 | 0 |
So “structure-forced” was never a property of the graphs — it was a gap in the toolkit. With the boundary bound added, every tight graph on at most 10 vertices has its tightness certified by a lower bound, with nothing left over.
That invites a much stronger question, and the answer on the range we can check is striking: p(G) equals the best of these bounds for every one of the 273,192 connected graphs on at most 9 vertices — 12,112 up to 8 vertices and all 261,080 at 9 vertices, with no gaps at all. If that identity held in general it would imply Gallai by induction: for any cut with b ≥ 1, using p(G[S]) ≤ ⌈|S|/2⌉ and p(G[V∖S]) ≤ ⌈|V∖S|/2⌉ on the smaller sides gives 2p(G[S]) + 2p(G[V∖S]) − 2b ≤ (|S|+1) + (|V∖S|+1) − 2b ≤ n. So the identity is at least as strong as the conjecture — which is also why it will not be easy.
One consistency check worth stating: since p(G) = 1 exactly when G has a Hamiltonian path, no polynomial-time family of bounds can equal p(G) unless P = NP. The boundary bound escapes that only because it is recursive. The recursion is essential, not an artifact.
The Parity Axis
Every reduction in §4 inducts on the number of vertices, and they all hit the same wall. So we tried inducting on degree parityinstead, standing on Lovász's theorem.
All-odd graphs are completely rigid: p = n/2 exactly, and in every optimal decomposition each vertex ends exactly one path, so the path-ends form a perfect pairing of the vertex set. Any graph can be pushed into that class by toggling parity — pair up the even-degree vertices and flip each pair, deleting the edge if present and adding it if absent. Converting back to G costs nothing when an added edge is an end-edge of its path (deleting it merely shortens the path) or a deleted edge can be re-attached at a path end.
For every graph on even n and every perfect matching on its even-degree vertices, the toggled all-odd graph has an optimal decomposition in which every toggle is free.
Gallai needs only one good pairing; the data says every pairing is good. All 76,632 pairings across all 11,235 connected graphs on even n ≤ 8 worked, each with a decomposition of G rebuilt from the all-odd case and verified edge by edge; the first pairing tried sufficed for 10,893 of the 11,117 graphs at n = 8. A sampled sweep at n = 10 and thirteen adversarial all-even-degree families to n = 12 (Knminus a perfect matching, complete bipartite and tripartite, cycles and their squares) produced zero decided failures.
Like Theorem D this is a reformulation, not a shortcut. Its value is a rigid base class and a sharper falsification target: one decided (G, pairing) failure kills it. The natural first target is a single toggle, which is the classical cycle-absorption obstruction in miniature.
A negative result on the record: the natural two-endpoint strengthening that would make a self-contained induction work is false — it fails for 25 of 758 instances at n ≤ 6, and 6 of those failures involve only vertices of degree ≥ 3, so it is not an artifact of the degree-2 vertices the splice removes.
Corrections On The Record
This campaign carried the caveat “the literature cannot be checked from this environment” for several turns. That was simply wrong, and checking it demoted two of our own headline claims. Both are kept here rather than deleted.
1. Verification at 11 vertices is not a frontier extension.Botler, Cunha and Sambinelli published it in 2019 using an integer-programming model. We had called it “the frontier” and hedged with “no priority claimed”; the accurate statement is that it was already done, and our sweep is an independent replication by a different method. That is still worth something — an ILP verification asks you to trust a solver, while ours emits a checkable certificate for every one of 577 million graphs — but it is not new.
2. Our “new structural finding” is a named open problem. Tight graphs at odd order being Knminus at most (n−3)/2 edges is exactly the Bonamy–Perrett question about odd semi-cliques. Our celebrated “prediction” of 20 tight graphs at 11 vertices was, unknowingly, counting the odd semi-cliques on 11 vertices — it landed exactly because it is a definition, not a forecast. What stands is independent computational evidence for a live question.
3. Everything else is treated as folklore. The splitting, parity and orbit lemmas, the endpoint property, the degree-2 splice and the parity toggling are all elementary. We could not find the boundary bound of §6 or the Free Toggle statement in print, but four web searches are weak evidence of novelty for a sixty-year-old problem — so they are offered, not claimed.
The standing instruction that came out of this, now at the top of our research log: check the literature first. One turn was spent naming and localising a property that already had a name, a literature, and known partial results.
The Reading List
- L. Lovász, On covering of graphs (1968) — the paths-and-cycles theorem that everything here stands on.
- F. Botler, M. Cunha, M. Sambinelli — On Computing the Path Number of a Graph (ENTCS 346, 2019) — the ILP model, and the verification of all graphs on ≤ 11 vertices that our sweep replicates.
- M. Bonamy, T. Perrett — Gallai's path decomposition conjecture for graphs of small maximum degree — Δ ≤ 5, and the source of the odd semi-clique question.
- F. Botler et al. — Towards Gallai's path decomposition conjecture — structure of the even-degree subgraph, the modern line of attack.
- Gallai's conjecture and the path number of odd semi-cliques (Discrete Mathematics, 2025) — work directly on the class our odd-order tables enumerate.
- Blanché, Bonamy, Bonichon — Gallai's path decomposition in planar graphs — the planar case, where K₃ and K₅ − e are the only odd semi-cliques.
- Gallai's path decomposition for 2-degenerate graphs — another class, and a clear write-up of the standard toolkit.
- In this repository: research/RESEARCH.md holds the full campaign log including dead ends and corrections; research/gallai-*.ts are the verifiers, each exiting non-zero if any certificate fails.