Graph theory · path decompositions · extremal combinatorics

Gallai’s Path-Decomposition Conjecture

Collaboration beta

Can the edges of every finite connected simple graph be partitioned into at most half as many simple paths as vertices, rounded up?

p (G) \leq ⌈ \frac{| V (G) |}{2} ⌉

Erdős Problems, Problem 583

Known results and sources

Simple paths thread a connected graph; the conjecture asks whether no more than ⌈|V|/2⌉ are ever needed.

Research problem

Exact mathematical statement

For a finite connected simple graph $G$ , let $p(G)$ be the minimum number of nonempty simple paths whose edge sets partition $E(G)$ . Then

p(G) \le \left\lceil \frac{|V(G)|}{2} \right\rceil.

A path is simple; trails, walks, circuits, and disconnected degree-two subgraphs do not automatically count as paths.

Problem infographic

Problem at a glance

A forest-green mathematical plate introduces Gallai’s path-decomposition conjecture with a connected simple graph, three differently patterned simple-path ribbons, the open inequality p(G) ≤ ceil(|V(G)|/2), and an exact equality example: the five-leaf star K₁,₅ has six vertices, five edges, and a three-path edge decomposition. — Gallai’s open conjecture asks whether every finite connected simple graph can have its edges partitioned into at most ceil(|V(G)|/2) nonempty simple paths. The star K₁,₅ meets the proposed bound with three paths.

Current mathematical picture

Where work on Gallai’s Path-Decomposition Conjecture stands

Open conjecture

This curated overview retains the current work's exact universal reformulations, atomic marked-obstruction reductions, degree-two activation models, exact clean-ladder frontier, independently cross-checked seven-rung mobile defect, and defect-matching accounting. The preferred route now asks for bounded local cell defect, bounded or sublinear matching deficiency, and a protected-endpoint-preserving cycle-wide rotation whose transition graph is acyclic. Gallai's conjecture remains open, the hand proofs still need external audit, and the finite searches do not settle the general statement.

Strongest supported footholdCritical locks and multi-leaf lens supply

The two one-mark regimes force edge-local repeated-contact locks, and deleting two leaves from a three-leaf minimum violator produces a tight two-mark collision state.

Evidence posture · Reported result

Leading routeCanonical cell extraction and bounded local defect

Define the cells actually produced by a minimum three-marked state, including ideal cost, protected endpoints, and admissible defect contacts, then prove a bounded local defect theorem for all of them.

Route status · Active route

Useful failureUniversal zero-overhead clean-ladder activation

The exact seven-rung obstruction eliminates the all-rank zero-overhead induction target; the viable replacement is bounded mobile defect.

Route status · Refuted route

Main reductionExact defect matching accounting

Certified pairwise cancellations now leave exactly q−2ν(F) unmatched cells before any multi-cell rotation, turning qualitative cancellation into an explicit upper-bound mechanism.

Evidence posture · Reported reduction

Completed special caseSeven-rung mobile unit defect

The displayed rank-seven residual has path number three, with one repeated endpoint movable exactly to x or any of the fourteen rung vertices, and not to c,a,b,v,s.

Evidence posture · Computation reproduced · provisional

Evidence footholdClean ladders through six

The retained exact C++ search reports that every normalized clean alternating ladder of ranks one through six has a two-path decomposition, covering 533,417 permutation-pair cases with zero failures.

Evidence posture · Computation reproduced · provisional

Priority open bridgeFormalize cell extraction and bounded local defect

Define canonical cells in a lexicographically optimal three-marked decomposition and prove each produced cell has zero or bounded local defect with explicit admissible contacts and protected endpoints.

Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Gallai’s Path-Decomposition Conjecture in numbers

6.8kretained lines of mathematical investigation6,805 in the current working snapshot

Argument development: 5,103 · 75%
Explored or eliminated routes: 539 · 8%
Computational analysis: 252 · 4%
Open obligations: 470 · 7%
Definitions and setup: 441 · 6%

23selected mapped statements11routes investigated10reported milestones7open questions5contribution-ready tasks

Evidence attached to the current work2 independent implementations agree1 original computation rerun16 manually checked claims

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byTibor Gallai, Paul ErdősProposed1966Status checkedAug 2, 2026

Recommended next task

Formalize cell extraction and bounded local defect

Suggested move: Define ideal cost, defect number, protected endpoints, and admissible defect locations, then test the definition against the retained seven-rung cell and the atomic repeated-intersection sources.

What would count as progress

Every extracted cell has an unambiguous edge set and does not double-count edges.
Each cell has an explicit ideal cost, protected endpoint set, and allowed defect locations.
A proved zero-overhead or bounded-defect theorem covers every cell produced by the extraction.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

27 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeCanonical cell extraction and bounded local defect

Route status · Active route

Active routeIdentified defect routing

Use mobile local defects, a compatible cancellation graph, directed double-shadow dependencies, and cycle-wide rotations to leave only bounded or sublinear unmatched defect.

Route status · Active route

Active routeShortest dependency-cycle rotation

Rotate simultaneously around a shortest directed dependency cycle while preserving edge occurrences, endpoint ownership, path simplicity, and the retained marked matching, and force the path-piece transition graph to be acyclic.

Route status · Active route

Active routeGeneral clean-cell defect frontier

Extend exact searches beyond rank seven by minimum defect and admissible defect location, seeking either a two-defect cell or a general unit-defect pattern with compact certificates.

Route status · Active route

Explored alternatives

Other routes

7 recorded

Narrowed routePairwise unit-defect cancellation

The exact matching formula now accounts for every certified disjoint pair, reducing the unresolved global question to matching deficiency and arm compatibility rather than qualitative cancellation language.

Route status · Narrowed route

Narrowed routeDefective four-common closure

Carry one labeled unit defect through the inherited clean four-common closure and compose two defective closures without losing marked incidence.

Route status · Narrowed route

Route held in reserveConditional dense alternate routes

The pure-nine terminal closure and simultaneous two-layer Walecki directions remain conditional secondary routes and should be pursued only if the universal defect route stalls.

Route status · Route held in reserve

Browse 4 more explored routes

Refuted routeUniversal zero-overhead clean-ladder activation

The exact seven-rung obstruction eliminates the all-rank zero-overhead induction target; the viable replacement is bounded mobile defect.

Route status · Refuted route

Useful but insufficientBridge-only buffer

Forest contacts can saturate the deletion lower bound, so a bridge-only construction cannot guarantee the final global saving.

Route status · Useful but insufficient

Refuted routeUntracked local splices

Checking each local concatenation for simplicity is insufficient because the global transition graph can close into a circuit.

Route status · Refuted route

Eliminated routeRoot-only neutral padding

The exact neutral-padding identity preserves defect and therefore cannot unlock a failing rooted profile.

Route status · Eliminated route

Route statements and reductions

Statements the next route can inspect and build on

Route statementAtomic obstruction core

Every bridge of an atomic marked obstruction is pendant, and deleting all pendant leaves leaves a 2-connected noncycle core with the current work's short degree-two restrictions.

Manually checked · provisional

Route statementClean ladders through six

The retained exact C++ search reports that every normalized clean alternating ladder of ranks one through six has a two-path decomposition, covering 533,417 permutation-pair cases with zero failures.

Computation reproduced · provisional

Route statementSeven-rung mobile unit defect

The displayed rank-seven residual has path number three, with one repeated endpoint movable exactly to x or any of the fourteen rung vertices, and not to c,a,b,v,s.

Computation reproduced · provisional

Route statementBounded or sublinear cubic defect suffices

A uniform O(1) or o(k) error in cubic Three-Port Compression implies exact Gallai; it is enough to prove such a bound on the cubic leaf-block-tree amplifier class.

Manually checked · provisional

Route statementBounded local defect for extracted cells

Every cell produced by canonical extraction from a lexicographically optimal three-marked state admits either zero-overhead closure or a bounded-defect decomposition with a nonempty admissible contact set and protected endpoints.

Source-reported route statement · dependencies incomplete

Route statementProtected cycle-wide rotation

Every shortest closed double-shadow dependency cycle admits a simultaneous rotation that preserves path simplicity and edge occurrences, ensures protected marked endpoints survive, and preserves the retained marked matching while leaving an acyclic path-piece transition graph.

Source-reported route statement · dependencies incomplete

Route statementIdentified defect routing

Local decompositions and defect locations can be chosen so that the cell-cancellation graph has O(1) or o(k) matching deficiency, every arm incompatibility enters a directed dependency graph, and shortest dependency cycles rotate without creating transition circuits.

Source-reported route statement · dependencies incomplete

Route statementTransition acyclicity is mandatory

Local simplicity of every splice does not guarantee a global path decomposition: a cyclic path-piece transition component expands to a circuit unless one transition is deliberately broken and charged.

Manually checked · provisional

Route statementProtected marked-endpoint invariant

A defect move may not consume a marked-matching endpoint, and it must preserve or increase the marked endpoint-incidence matching number; ordinary path savings alone do not control Φ.

Manually checked · provisional

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

7 featured tasks

Formalize cell extraction and bounded local defect

Ready to work on

Determine the general clean-cell defect frontier

Extend the exact clean-ladder search beyond rank seven while minimizing defect, and find either the first two-defect clean cell or evidence supporting a universal unit-defect theorem in the exact clean model.

Suggested move: Search ranks beyond seven by minimum defect and produce compact certificates rather than only exhaustive path catalogs.

Ready to work on

Independently audit the v12 hand proofs

Line-audit the full one-mark, bridge/core, pendant-stripping, degree-two, and two-link amplifier arguments and explicitly withdraw or repair any failed step.

Suggested move: Audit odd/odd bridge splicing, core order boundaries, the marked-support leaf formula, equal-neighbor suppression, and every amplifier lower bound.

Ready to work on

Strengthen finite-result certification

Independently rewrite the positive clean-ladder frontier search, produce a compact certificate for the rank-seven no-two-path result, and formalize or certificate-check the defect-profile verifier.

Suggested move: Start with an implementation-independent compact certificate for the displayed rank-seven obstruction, then independently reproduce the positive rank-six census.

Ready to work on

Carry a defect through four-common closure

Extend the inherited all-rank clean four-common theorem to a closure with one labeled unit defect, then prove that two such closures compose and cancel without losing marked incidence.

Suggested move: Seek a Hamilton-closure statement in which one factor remains open with a labeled defect edge.

Ready to work on

Construct an acyclic cycle-wide rotation

On a shortest directed double-shadow dependency cycle, construct a simultaneous rotation whose path-piece transition graph is acyclic and whose retained marked matching, edge occurrences, and endpoint ownership survive.

Suggested move: Work on a shortest directed dependency cycle and explicitly track every path piece, protected endpoint, edge occurrence, and transition component.

Blocked by the current route

Bound compatible-cell matching deficiency

Prove that the compatible cell-cancellation graph has matching deficiency O(1) or o(k), using endpoint surplus, support-endpoint balance, a Hall witness, or admissible rotations.

Suggested move: After canonical cell extraction is fixed, translate arm incompatibilities into directed double-shadow dependencies and search for a Hall-type deficiency bound.

Blocked by the current route

Sourced mathematical context

The known mathematical landscape

Context collected Aug 2, 2026

Current statusOpen conjecture

The conjecture that every connected n-vertex simple graph has an edge partition into at most ceil(n/2) simple paths remains open. The best general bound is floor(2n/3); many major graph classes satisfy the conjectured bound.

[11][16]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026
Peer reviewedRecent work proves further odd-semiclique cases while retaining floor(2n/3) as the best general bound.[11]
2024
Peer reviewedThe conjecture was proved for all 3-degenerate graphs.[9]
2024
Peer reviewedThe conjecture was proved for graphs of treewidth at most four.[8]
2020
Peer reviewedThe conjecture was proved for graphs of treewidth at most three, with K3 and K5-e classified as the exceptions to the stronger floor(n/2) bound.[2]

Mathematical neighborhood

Related results and reusable starting points

Current focusGallai's path decomposition conjecture

Stronger or generalized formodd-semiclique path-decomposition conjecture

A stronger classification asks for floor(n/2) paths except for the odd-semiclique edge-count obstructions; it remains open in general.

[11]

Equivalent formulationLovász path-and-cycle decomposition theorem

Lovász allows cycles as pieces; it implies Gallai for important parity classes but is not the conjecture itself.

[18]

Equivalent formulationHajós cycle-decomposition conjecture

Hajós concerns decomposing Eulerian graphs into cycles, not all connected graphs into paths.

[1]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

computation · source linked; not reproduced by ProofAtlasPeer Reviewed Exhaustive Check
An exact ILP study verified the conjecture for all graphs through 11 vertices, bipartite graphs through 16 vertices, and regular graphs through 14 vertices; no public source repository was located in this pass.
[12]
computation · source linked; not reproduced by ProofAtlasAlgorithmic Complexity
Computing path number is NP-hard even under strong restrictions, while exact computation is tractable for subcubic graphs and fixed-parameter tractable by distance to subcubic graphs.
[15]

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

10 mapped milestonesretained argument map

Browse all 10 mapped stages

stage 1Exact rooted and marked reformulations
stage 2Atomic marked obstruction and core collapse
stage 3Critical locks and multi-leaf lens supply
stage 4Degree-two activation and non-cut amplifier
stage 5Exact clean-ladder census through rank six
stage 6Universal zero-overhead clean activation eliminated
stage 7Rank-seven obstruction has a mobile unit defect
stage 8Exact matching-deficiency accounting
stage 9Global splices must track transitions and protected endpoints
stage 10Current frontier: bounded local defect and cycle-wide routing

Exact rooted and marked reformulationsThe current work replaces the global path bound by exact Strict-Leaf, rooted activation, cubic compression, and marked endpoint objectives.