Problem 583

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

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Falsifiable, the site's label for an open statement that a finite counterexample would refute; the standing here is open. A counterexample would be a connected graph on $n$ vertices whose every path decomposition has more than $\lceil n/2\rceil$ paths, a property that finite enumeration decides for any given graph. No proof for all connected graphs and no counterexample is known. The conjecture is proved for connected graphs of maximum degree at most $5$ (Bonamy and Perrett, Theorem 1.3; Discrete Math. 2019, refereed; claim page (Bonamy and Perrett, 2016)), for connected planar graphs (Blanché, Bonamy and Bonichon, Theorem 1.1; an extended abstract of 2021 and a 2022 preprint whose full proof has no journal version found; claim page (Blanché, Bonamy and Bonichon, 2021)) and for connected $2$ -degenerate graphs (Anto and Basavaraju, Theorem 1; DMTCS 2023, refereed; claim page (Anto and Basavaraju, 2022)), and, with $\lfloor n/2\rfloor$ paths, for graphs in which every cycle contains a vertex of odd degree, that is, whose even-degree vertices induce a forest (Pyber, Theorem 0; J. Combin. Theory Ser. B 1996, refereed; claim page (Pyber, 1996)), and, with $\lfloor n/2\rfloor$ paths, for graphs each block of whose even-degree subgraph is a triangle-free graph of maximum degree at most $3$ (Fan, Corollary; J. Combin. Theory Ser. B 2005, refereed), and more generally for graphs whose even-degree subgraph is an $\alpha$ -graph (Fan, Main theorem; claim page (Fan, 2004)), and, with $\lfloor n/2\rfloor+1$ paths, hence $\lceil n/2\rceil$ when $n$ is odd, for graphs whose even-degree vertices induce a complete graph $K_m$ with $m\le15$ (Chu, Fan and Zhou, Theorem 1.3; Discrete Math. 2026, refereed; claim page (Chu, Fan and Zhou, 2025)), and, second-hand through the cited papers' introductions and the site, for Lovász's class (at most one vertex of even degree; a proceedings paper; claim page (Lovász, 1968)), among others. An exhaustive computer check for $n\le11$ is reported in the site's discussion thread (claim page (sallerk, 2026)) and reproduced there with an independent decider (claim page (herong, 2026)); both are claimed partial results, not sources of status.

Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97--109; item 11, p. 101. Library home: Erdős 1971 (a scan); the passage is paged at Erdős 1971, Item 11 (pp. 101-102).
BoPe19: Bonamy, Marthe and Perrett, Thomas J., Gallai's path decomposition conjecture for graphs of small maximum degree. Discrete Math. 342 (2019), no. 5, 1293--1299, doi:10.1016/j.disc.2019.01.005 (Crossref record read; not held); pages cited from arXiv:1609.06257v1 (20 September 2016, pagination 1--11). Conjecture 1.1 and the quoted Theorems 1.1--1.2, p. 1; Theorem 1.3 and Question 1.1, p. 2. Library home: Bonamy and Perrett 2019.
BBB21: A. Blanché, M. Bonamy, and N. Bonichon, Gallai's path decomposition in planar graphs. arXiv:2110.08870 (v1 17 October 2021; v2 21 June 2022, 95 pp.). An extended abstract appeared in Extended Abstracts EuroComb 2021 (Trends in Mathematics), 758--764, doi:10.1007/978-3-030-83823-2_121 (not held). Theorems 1.1--1.2, p. 1. Library home: Blanché, Bonamy and Bonichon 2021.
AnBa23: Anto, Nevil and Basavaraju, Manu, Gallai's path decomposition for 2-degenerate graphs. Discrete Math. Theor. Comput. Sci. 25:1 (2023), Paper No. 16, 11 pp., doi:10.46298/dmtcs.10313 (accepted 4 May 2023, published 30 May 2023; arXiv:2211.07159v3 is the paper in the journal's typesetting). Conjecture 1, p. 1; Theorem 1 and Corollary 1, p. 2. Library home: Anto and Basavaraju 2023.
CFZ26: Chu, Yanan and Fan, Genghua and Zhou, Chuixiang, Gallai's conjecture and the path number of odd semi-cliques. Discrete Math. 349 (2026), Paper No. 114725, 6 pp., doi:10.1016/j.disc.2025.114725 (received 18 December 2024, accepted 30 July 2025, available online 18 August 2025; the Crossref record read gives the issue date February 2026). Conjecture 1.1 and Theorem 1.2 (Lovász, quoted), p. 1; Theorems 1.3--1.5, the semi-clique definition, Conjecture 1.6 and Theorem 1.7, p. 2; the proof of Theorem 1.4, p. 6. Library home: Chu and Zhou 2026; the results are paged at Chu and Zhou 2026, Theorem 1.3 and Chu and Zhou 2026, Theorem 1.7.
Lo68: Lovász, L., On covering of graphs. Theory of Graphs (Proc. Colloq., Tihany, 1966) (1968), 231--236. Not held; quoted on p. 1 of [BoPe19], p. 1 of [AnBa23], p. 608 of [CFS14] (Theorem 1.1) and p. 2 of [BM22].
Py96: Pyber, L., Covering the edges of a connected graph by paths. J. Combin. Theory Ser. B 66 (1996), 152--159, doi:10.1006/jctb.1996.0012. Theorem 0 (the forest case) and Lovász's theorem and corollary, p. 152; the odd semi-clique Example, Gallai's Conjecture, Theorems I and II (the covering bounds) and the Example on asymptotic versions, p. 153; the derivation of Theorem 0, p. 155. Library home: Pyber 1996; the results are paged at Pyber 1996, Theorem 0 and Pyber 1996, Theorem I. Its forest theorem is also quoted as Theorem 1.1 of [BoPe19], in agreement with the printed statement.
Fa02: Fan, Genghua, Subgraph coverings and edge switchings. J. Combin. Theory Ser. B 84 (2002), 54--83, doi:10.1006/jctb.2001.2063 (Crossref record). Not held; the covering version, $\lceil n/2\rceil$ paths that may share edges, quoted from the site, p. 2 of [BM22] and p. 609 of [CFS14].
Fa05: Fan, Genghua, Path decompositions and Gallai's conjecture. J. Combin. Theory Ser. B 93 (2005), 117--125, doi:10.1016/j.jctb.2004.09.008. Not cited by the site. The abstract, p. 117; Gallai's conjecture as stated, the survey paragraph with Lovász's $\lfloor n/2\rfloor$ consequence and the disjoint-triangles example, and Definition 2.1 ( $\alpha$ -operations), p. 118; Definition 2.2 and Propositions 2.3--2.6 ( $\alpha$ -graphs), p. 119; the Main theorem, p. 124; the Corollary (the block condition), p. 125. Library home: Fan 2005; the results are paged at Fan 2005, Corollary and Fan 2005, Main theorem. Its Corollary is also quoted as Theorem 1.2 of [BoPe19], in agreement with the printed statement.
Ch78: Chung, F. R. K., On partitions of graphs into trees. Discrete Math. 23 (1978), 23--30, doi:10.1016/0012-365X(78)90183-8 (Crossref record). Not held; quoted from the site.
DeKo00: Dean, Nathaniel and Kouider, Mekkia, Gallai's conjecture for disconnected graphs. Discrete Math. 213 (2000), 43--54, doi:10.1016/S0012-365X(99)00167-3 (Crossref record). Not held; quoted from the site, p. 2 of [BM22] and p. 608 of [CFS14]. Yan's 1998 Arizona State University thesis, On path decompositions of graphs, is the independent source of the same bound per [BM22]; not held.
BM22: Bucić, M. and Montgomery, R., Towards the Erdős-Gallai cycle decomposition conjecture. arXiv:2211.07689v2 (2023); Adv. Math. 437 (2024), 109434. Its p. 2 surveys the path problem. Library home: Bucić and Montgomery 2022.
CFS14: Conlon, David and Fox, Jacob and Sudakov, Benny, Cycle packing. Random Structures Algorithms 45 (2014), 608--626. Theorem 1.1 (Lovász, quoted) and the paragraph on Gallai's problem, pp. 608--609. Library home: Conlon, Fox and Sudakov 2014.

Problem 583

Status

Proof claims

Discussion