ERDŐS/DAILY ▸

← back to the ledger

ERDőS #583 · PARTIAL

Erdős problem 583 — wave9t report

Date of live-page check and computation: 2026-07-28 UTC.

Claim labels used throughout:

cited published theorem.

but not a proof.

but not promoted to a theorem independent of the computation and nauty.

Result in one paragraph

The live page triggered no stop condition: it says FALSIFIABLE, explicitly describes the status as open, has 0 claimed proofs, and has None under “Currently working on this problem.” (a: direct live-page observation) I computed the exact path number of every connected unlabeled simple graph through eight vertices. The exact distributions are given below; in particular the conjectured bound holds throughout this range. (d) More sharply, through eight vertices the only connected graphs needing more than \(\lfloor n/2\rfloor\) paths are precisely the odd semi-cliques, verifying the stronger Bonamy–Perrett question in this range. (d) This does not prove a uniform statement and does not close problem 583.

Step 0: authoritative live page

I fetched the live page and its discussion thread through a Bright Data residential browser because direct datacenter access is Cloudflare-walled. The page reported that it was last edited 2026-04-01. (a: direct live-page observation)

Verbatim statement

Every connected graph on \(n\) vertices can be partitioned into at most \(\lceil n/2\rceil\) edge-disjoint paths.

That is the complete displayed statement on the live page. The page cites Erdős [Er71, p. 101]. In the original scan, p. 101 says that Erdős and Gallai considered whether every connected \(n\)-vertex graph is the union of \(\lfloor(n+1)/2\rfloor=\lceil n/2\rceil\) edge-disjoint paths. (a: source transcription and integer identity)

Status, claimed proofs, and markers

The live page displayed all of the following. (a: direct live-page observation)

notice calls the status open.

Thus neither of the mandatory collision/duplication stop conditions applied.

Known results listed by the live page

The following is a faithful transcription in condensed prose; I treat it as page-provided ground truth, as requested.

\(\lfloor n/2\rfloor\) edge-disjoint paths and cycles, hence at most \(n-1\) paths. This gives the conjecture when at most one vertex has even degree.

edge-disjoint trees.

edge-disjoint, and proves the original conjecture when the subgraph induced by even-degree vertices is a forest.

\(K_m\), \(m\leq15\), and \(n\) is odd.

\(\lceil2n/3\rceil\) paths even for disconnected graphs, optimally there, and that Yan independently obtained the same bound in a 1998 thesis.

partitioned into at most \(\lfloor n/2\rfloor\) edge-disjoint cycles.

There is a rounding discrepancy worth preserving rather than silently “correcting”: the first forum comment and recent primary literature state the Dean–Kouider bound as \(\lfloor2n/3\rfloor\), whereas the current main page renders \(\lceil2n/3\rceil\). Dean–Kouider's sharper formula is \(\tfrac12u+\lfloor\tfrac23g\rfloor\), with \(u\) odd-degree and \(g\) nonisolated even-degree vertices, and implies the floor version. See DOI 10.1016/S0012-365X(99)00167-300167-3). (b)

All three live comments

The discussion page displayed three comments and warned that comments are the users' responsibility and are not verified by the site. (a: direct live-page observation)

  1. Woett, 2026-03-16 13:29: identified Dean–Kouider's

\(\lfloor2n/3\rfloor\) bound as apparently best without restrictions, noted that it applies and is optimal for disconnected graphs, and said that Yan's thesis could not then be found online. The comment says the site was updated in response.

  1. JakeMallen, 2026-03-16 14:13: “I've uploaded Yan's paper here.”
  2. Alfaiz, 2026-03-04 14:27: listed Pyber's even-vertex-induced-forest case,

Geng–Fang–Li for maximal or 2-connected outerplanar graphs, Bonamy–Perrett for maximum degree 5, Blanché–Bonamy–Bonichon for planar graphs, and Chu–Fan–Liu for maximum degree 6 when maximum-degree vertices are independent, subject to exceptions. This comment also says the site was updated in response.

No comment claimed a proof of the unrestricted conjecture and none named a current worker. (a: direct live-page observation)

Literature audit beyond the page

I searched by the exact conjecture name, its “path number” terminology, the even-degree induced-subgraph formulation, recent years 2024–2026, and the authors in the page bibliography. I verified the following identifiers against the primary paper or publisher abstract; I did not find a primary source claiming the unrestricted conjecture is solved or falsified.

author-hosted scan. (a)

JCTB 66 (1996), DOI 10.1006/jctb.1996.0012; its abstract states the \(n/2+O(n^{3/4})\) result. (b)

10.1016/j.disc.2019.01.005. (b)

arXiv:2110.08870, whose abstract says it proves the conjecture for every planar graph. (b)

DOI 10.46298/dmtcs.10313 and arXiv:2211.07159. It proves the stronger \(\lfloor n/2\rfloor\) bound except for the triangle. (b)

2024: Zhang–Liu–Hong, Gallai's conjecture for 3-degenerated graphs, DOI 10.1016/j.disc.2024.114057. Its Theorem 1.3 proves the stronger non-odd-semi-clique statement for 3-degenerate graphs, hence problem 583 for every 3-degenerate graph. (b)

the path number of odd semi-cliques, DOI 10.1016/j.disc.2025.114725, published in the February 2026 issue of Discrete Mathematics*. Its abstract states exactly the \(E(G)\cong K_m\), \(m\leq15\), result described by the live page. (b)

arXiv:2510.12806 and DOI 10.1016/j.disc.2025.114830. It still calls the unrestricted assertion a conjecture and proves a \(3n/5\) bound for an Eulerian restricted class in which distinct triangles have distance at least 3. (b)

arXiv:2409.06298, updated 2026-03-22; it proves the Gallai bound for the stated Levi graphs, not for arbitrary connected graphs. (b)

This search is not a proof that no other paper exists. It is evidence that the live open status is consistent with the recent primary literature located. (c)

Exact computation

Let \(p(G)\) be the minimum number of nonempty simple paths whose edge sets partition \(E(G)\). Paths may share vertices but not edges.

Elementary lower bounds

For any residual component \(H\) with at least one edge, every path decomposition needs at least

\[ L(H)=\max\left\{ \frac{o(H)}2,\ \left\lceil\frac{\Delta(H)}2\right\rceil,\ \left\lceil\frac{|E(H)|}{|V(H)|-1}\right\rceil,\ 2\mathbf 1_{\{o(H)=0\}} \right\}. \]

Here \(o(H)\) is the number of odd-degree vertices. The four terms follow, respectively, because path endpoints must supply every odd degree, a single path has degree at most two at a vertex, a simple path has at most \(|V(H)|-1\) edges, and a nonempty Eulerian component is not one open path. Paths cannot cross different residual components, so these component bounds add. (a)

Exhaustive algorithm

For each \(n\), the checker first enumerates every nonempty unoriented simple path of \(K_n\). There are

\[ \frac12\sum_{\ell=1}^{n-1}\frac{n!}{(n-\ell-1)!} \]

such paths; the program independently checks that it generated exactly this many distinct edge masks. (a for the formula; d for the check)

For a graph edge mask \(R\), the exact-cover recursion is:

search(R,k):
    reject if the additive lower bound L(R) exceeds k
    choose a fixed uncovered edge e
    for every simple path P with e in P and E(P) contained in R:
        accept if search(R minus E(P), k-1) accepts

This is exhaustive: in any decomposition, exactly one member contains the chosen edge \(e\), and that member occurs in the loop. Removing its edge mask leaves precisely the same problem on the remaining edges. Conversely, every accepting branch returns edge-disjoint simple paths with union \(E(G)\). Trying \(k\) in increasing order therefore returns \(p(G)\). (a: correctness of the finite recursion)

The program then independently reconstructs every returned path as a vertex sequence and checks: nonempty; no repeated vertex; no nonedge; pairwise edge-disjoint; union exactly \(E(G)\). (d)

Connected unlabeled graphs are streamed from Brendan McKay's nauty-geng -cq. The program asserts the standard connected-isomorphism-class counts \(1,1,2,6,21,112,853,11117\) for \(n=1,\ldots,8\), hashes each graph6 stream, and solves every emitted graph. Thus completeness is rigorous modulo the documented correctness of nauty's geng; the mathematical conclusions remain classified (d).

Exact table

Blank entries are zero.

| \(n\) | connected classes | \(p=0\) | \(p=1\) | \(p=2\) | \(p=3\) | \(p=4\) | \(\max p(G)\) | |---:|---:|---:|---:|---:|---:|---:|---:| | 1 | 1 | 1 | | | | | 0 | | 2 | 1 | | 1 | | | | 1 | | 3 | 2 | | 1 | 1 | | | 2 | | 4 | 6 | | 1 | 5 | | | 2 | | 5 | 21 | | 1 | 18 | 2 | | 3 | | 6 | 112 | | 1 | 64 | 47 | | 3 | | 7 | 853 | | 1 | 282 | 566 | 4 | 4 | | 8 | 11,117 | | 1 | 1,424 | 8,408 | 1,284 | 4 |

Every row has \(\max p(G)=\lceil n/2\rceil\) for odd \(n\ge3\) and \(\max p(G)=n/2\) for even \(n\); hence problem 583 holds for \(n\le8\). (d)

As an implementation cross-check, before writing the standalone program I ran a separate graph-specific path enumerator over NetworkX's independent graph_atlas_g() data through \(n=7\). It returned the same connected-class counts and the same five nontrivial distribution rows \(\{1:1,2:1\}\), \(\{1:1,2:5\}\), \(\{1:1,2:18,3:2\}\), \(\{1:1,2:64,3:47\}\), and \(\{1:1,2:282,3:566,4:4\}\) for \(n=3,\ldots,7\), respectively. The \(n=8\) result uses geng, because the NetworkX atlas stops at seven vertices. (d)

Stronger odd-semi-clique classification

An odd semi-clique on \(n=2k+1\) vertices is obtained from \(K_n\) by deleting at most \(k-1\) edges, equivalently \(|E(G)|>k(n-1)=\lfloor n/2\rfloor(n-1)\). Since each simple path has at most \(n-1\) edges, every odd semi-clique needs at least \(k+1=\lceil n/2\rceil\) paths. (a)

The exhaustive computation found exactly seven isomorphism classes with \(p(G)>\lfloor n/2\rfloor\), and they are exactly the seven odd semi-cliques through order eight. (d)

| \(n\) | graph6 code | edges | exact \(p(G)\) | |---:|:---|---:|---:| | 3 | Bw | 3 | 2 | | 5 | D^{ | 9 | 3 | | 5 | D~{ | 10 | 3 | | 7 | FV~~w | 19 | 4 | | 7 | F]~~w | 19 | 4 | | 7 | F^~~w | 20 | 4 | | 7 | F~~~w | 21 | 4 |

For the two 19-edge graphs, the two deleted edges are adjacent in one class and disjoint in the other. The 20- and 21-edge classes delete one and zero edges. This accounts for all four 7-vertex odd semi-cliques. (a) The standalone checker prints and validates an explicit optimal path decomposition for every row. (d)

Reproducibility digests

Environment: Python 3.12.3, nauty Debian package 2.8.8+ds-5. The script SHA-256 at the audited run was dfd4964543cf91d5b99c12efc39290eda909ca4a69fd45511f93c11c651ce5a7.

The graph6-stream SHA-256 values were:

n=1  ecf5de1a2ecc66a1876a832804c64f6b5125784e94c82285d9720621c613ab46
n=2  fae4bfc454bd04363dcd5222772f2973b1193e1ff6f676e822a427323a677ef9
n=3  5966edf890849db6cb03626431916231a81a30c9db9a4781a4a8f2e5dc7e6129
n=4  d7da485669f2dc74b81c02f18774a07430937684896833d59f138b10debb5005
n=5  8169b01acd1570bf0d464cb7b4cf17ebb263035dc664de84ce41b8dd9618e301
n=6  9fd4d2161400fc5f302fe1adc8c2b1230c312a15b15d0e2a343a02d75dd5cbfa
n=7  eca7b9f61b5f54fe98f23f8b4e2baf77be08cd392911e0655fc8b7a72640fae1
n=8  37010dfb9ca35c86bcbfd488c3e4cadcb3e918dc8c6acebd81ea966e79c35a84

The deterministic aggregate graph/path-certificate SHA-256 was 862afb81148d4e1cb644205d8e50823ffb836fac84fd15e1acec887cd61d9aa4. The final complete rerun took 23.131 seconds and ended ALL CHECKS PASSED. (d)

Audit of a larger online computational claim

A December 2024 blog post, Verifying Gallai's Path Conjecture for Small Graphs, reports a check through 11 vertices. This is not a primary research paper. Its linked GitHub repository returned 404 on 2026-07-28, and the formulation printed in the post is a relaxation rather than a path-decomposition model. Specifically:

edges;

\(|E_p|\le |V_p|-1\) does not force color \(p\) to be connected, and with unsupported vertex variables it does not even force acyclicity;

vertex, so it can output a trail or cycle rather than a simple path.

These are direct logical gaps in the displayed certificate conditions; they do not show that the claimed conclusion through 11 is false, only that the posted method does not verify it. (a)

There is a six-vertex regression showing that connectivity is essential. Let

\[ E(H)=\{01,02,03,34,35,45\}, \]

whose graph6 code is EsCW. Its edges split into two linear forests:

\[ \{02,03,35,45\},\qquad \{01,34\}. \]

The first is the path \(2-0-3-5-4\); the second is a disconnected union of two edges. Thus a two-color “linear forest” relaxation accepts. (a)

Yet \(p(H)=3\). The odd vertices are \(0,1,2,3\), so two paths would have to use exactly those four endpoint incidences, leaving even vertices 4 and 5 as endpoints zero times. If neither 4 nor 5 is an endpoint, the two incident triangle edges at each must lie consecutively in one path. The shared edge 45 then forces all three edges of triangle 345 into one path, impossible. Hence two paths do not suffice. The three paths

\[ 1-0-2,\qquad 0-3-4-5,\qquad 3-5 \]

do suffice. Therefore \(p(H)=3\). (a) The supplied program independently checks this regression and prints two_linear_forests_components=(1,2) PASS. (d)

Consequently I do not use the blog's \(n\le11\) number as an established computational result; the exact table in this report stops at \(n=8\).

What remains and why this run stops

The computation has no uniformity step: checking finitely many isomorphism classes cannot settle the conjecture for arbitrary \(n\). (a) The exact theoretical obstruction is not finding paths in one fixed graph; it is proving a reduction that always finds a removable simple path (or a bounded packet of paths) whose deletion reduces the induction parameter by at least two vertices and whose residual components can be recombined without exceeding the global \(\lceil n/2\rceil\) budget. Sparse-class proofs obtain such removable structures from degeneracy, planarity, or restrictions on the even-degree induced subgraph. No located theorem guarantees one in an arbitrary dense even-degree core. (b for the cited restricted results; c for this diagnosis)

Equivalently, Lovász's path-and-cycle decomposition leaves a cycle-splicing problem: naively splitting every residual cycle can add too many paths. A uniform lemma pairing or absorbing all those cycles into existing paths within the endpoint budget would bridge the central gap. No such general lemma was found. (c)

Extending the same exact computation to \(n=9\) is heavier but quite feasible as a separate batch: there are 261,080 connected classes rather than 11,117, and \(K_9\) has 493,200 simple path masks (3,452,436 edge incidences) rather than 54,796 (328,804 incidences). Scaling the measured \(n=8\) run by these two work factors gives about 1.6 core-hours; allowing for larger search trees, a realistic estimate is 2–5 core-hours, roughly USD 0.10–0.50 at USD 0.05–0.10 per core-hour. I did not run it because the task limits this box to a few CPU-minutes. (a for the exact counts; c for the cost extrapolation)

Reproduction

The standalone checker is runs/erdos583_wave9t_reverify.py. Run from the repository root:

python -m py_compile runs/erdos583_wave9t_reverify.py
python runs/erdos583_wave9t_reverify.py

It uses only the Python standard library plus the nauty-geng executable. The default full run regenerates every graph, every candidate simple path, every optimality search, all explicit decomposition checks, the stronger odd-semi-clique comparison, and the relaxation regression.

PARTIAL: Exact exhaustive path-number distributions and the stronger odd-semi-clique classification are verified for every connected simple graph on at most 8 vertices; no uniform proof or counterexample is obtained.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger