Fan 2005 path decompositions gallai s conjecture

../

corollary: Fan's block case of Gallai's conjecture: a graph on n vertices, connected or not, each block of whose even-degree subgraph is a triangle-free graph of maximum degree at most 3 decomposes into floor(n/2) paths, from the Main theorem and Proposition 2.6; the row Problem 583's table records for the paper.

main_theorem: Fan's Main theorem: a graph on n vertices, connected or not, whose even-degree subgraph is an alpha-graph, one built from the empty graph by adding isolated vertices and vertices joined to independent alpha-pairs, decomposes into floor(n/2) paths; alpha-graphs include the forests and the graphs of the Corollary.

---

Genghua Fan, Path decompositions and Gallai's conjecture, J. Combin. Theory Ser. B 93 (2005), 117--125, DOI 10.1016/j.jctb.2004.09.008 (printed at the foot of p. 117 with the copyright line "© 2004 Elsevier Inc."); received 23 August 2002, available online 11 November 2004 (p. 117); the author at the Department of Mathematics, Fuzhou University. Cited as [Fa05] on the problem page. Its seven references (p. 125): [1] Dean and Kouider, Gallai's conjecture for disconnected graphs, Discrete Math. 213 (2000), 43--54, the problem page's [DeKo00], not held; [2] Donald, An upper bound for the path number of a graph, J. Graph Theory 4 (1980), 189--201; [3] Fan, Subgraph coverings and edge-switchings, J. Combin. Theory Ser. B 84 (2002), 54--83, the problem page's [Fa02], not held, whose Lemmas 4.3 and 4.6 the present paper's Lemmas 3.3 and 3.5 specialize (p. 120); [4] Lovász, On covering of graphs, in Theory of Graphs (Academic Press, 1968), 231--236, the problem page's [Lo68], not held; [5] Pyber, Covering the edges of a graph by ..., Colloq. Math. Soc. János Bolyai 60 (1991), 583--610; [6] Pyber, Covering the edges of a connected graph by paths, J. Combin. Theory Ser. B 66 (1996), 152--159, filed as pyber_1996_covering_edges_connected_graph_paths; [7] Yan, On path decompositions of graphs, Ph.D. thesis, Arizona State University, 1998. Only [6] has a card here.

The copy read for this card is the publisher's production PDF of the printed article: 9 pages, printed pp. 117--125 = PDF pp. 1--9 (printed p. $n$ is PDF p. $n-116$), typeset pages of 468 by 680 points (the file's metadata names Acrobat Distiller 4.05 for Windows and a creation date of 25 January 2005), with a text layer that reads the prose cleanly but drops the Greek letter of the paper's $\alpha$-operations (they come out as "-operations") and the floor and ceiling brackets ($\lceil n/2\rceil$ and $\lfloor n/2\rfloor$ both come out as "n2"), so every statement below was checked on the page image. Provenance: the copy was obtained on 2026-09-22 from the publisher's open archive, the DOI https://doi.org/10.1016/j.jctb.2004.09.008 resolving to the article's page (PII S0095895604000875), whose PDF is served free under the publisher's open-archive user license; 237,392 bytes. The file prints "© 2004 Elsevier Inc. All rights reserved." on its first page. The license the Crossref record https://api.crossref.org/works/10.1016/j.jctb.2004.09.008 (read 2026-10-07) names for the published version is that user license, https://www.elsevier.com/open-access/userlicense/1.0/, whose terms (read the same day) permit non-commercial access, downloading and copying but not redistribution; every other right is reserved.

Read status: claims checked for the abstract (p. 117), the definitions of the E-subgraph and of a path-decomposition, Gallai's conjecture as the paper states it, the survey paragraph with the triangle example, and Definition 2.1 (p. 118), Definition 2.2 and Propositions 2.3--2.6 (p. 119), Lemma 3.5 (pp. 121--122) and Lemma 3.6 (p. 122), Lemma 3.7 and Lemma 4.1 (pp. 122--123), the Main theorem (p. 124) and the Corollary (p. 125), each read clause by clause on the page images of PDF pp. 1--3 and 6--9 (printed pp. 117--119 and 122--125) on 2026-09-22; the reference list (p. 125) was read on the page image. The derivation of the Corollary from Proposition 2.6 and the Main theorem (one sentence, p. 125) and the proofs of Propositions 2.4 and 2.5 (a paragraph each, p. 119) were read in full on the page images and followed. The proof of Proposition 2.6 (pp. 119--120), Definitions 3.1--3.2 and Lemmas 3.3--3.4 with the proof of Lemma 3.3 (pp. 120--121) were read in the text layer of PDF pp. 4--5 for structure only; the proofs of Lemmas 3.5--3.7 and 4.1 (pp. 122--124) and of the Main theorem (pp. 124--125) were read on the page images for structure only, as summarized on the result pages, and none of their steps was checked. On 2026-10-07 every statement this card and its result pages make about the paper was checked again on the page images of PDF pp. 1--9, including the opening of Lemma 3.5 on p. 121. Nothing here is independently reviewed.

Contents

• Abstract and § 1, Introduction (pp. 117--118). The abstract states Gallai's conjecture for a connected simple graph $G$ on $n$ vertices, a decomposition of its edges into $\lceil\frac n2\rceil$ paths, writes $H$ for the subgraph induced by the vertices of even degree, and recalls that Lovász proved the conjecture when $H$ has at most one vertex and Pyber when $H$ is a forest, that is, when every block of $H$ is a vertex or an edge and so has maximum degree at most 1. It then says that the conjecture holds when $H$ can be obtained from the empty set by the paper's $\alpha$-operations (the Main theorem) and, as a corollary, when each block of $H$ is a triangle-free graph of maximum degree at most 3. Graphs are finite, undirected and simple; a block is a maximal nonseparable subgraph (printed "maximum", p. 117); "The E-subgraph of $G$ is the subgraph induced by the vertices of even degree in $G$" (p. 118); a path-decomposition of $G$ is a set of edge-disjoint paths whose edge sets cover $E(G)$, trivial paths (single vertices) allowed, so a decomposition into at most $k$ paths can be padded to one into exactly $k$ (p. 118). The paper attributes the question, how many paths suffice to decompose every connected graph on $n$ vertices, to Erdős, and the conjectured answer $\lceil\frac n2\rceil$ to Gallai, citing Lovász [4] for both (p. 118). Gallai's conjecture (p. 118, quoted): "If $G$ is a connected graph on $n$ vertices, then $G$ can be decomposed into $\lceil\frac n2\rceil$ paths." The survey paragraph (p. 118): Lovász [4] decomposes every graph on $n$ vertices, connected or not, into $\lfloor\frac n2\rfloor$ paths and circuits; Donald [2] into $\lfloor\frac34n\rfloor$ paths, and Dean and Kouider [1] and Yan [7] independently lowered this to $\lfloor\frac23n\rfloor$; Lovász's theorem gives $\lfloor\frac n2\rfloor$ paths when at most one vertex of $G$ has even degree, that is, when the E-subgraph has at most one vertex, and Pyber [6] extended this to every $G$ whose E-subgraph is a forest. The paper then states its Corollary in advance, $\lfloor\frac n2\rfloor$ paths for a graph on $n$ vertices, connected or not, each block of whose E-subgraph is a triangle-free graph of maximum degree at most 3, and shows that triangle-freeness cannot be dropped: a graph made of $k$ vertex-disjoint triangles has $3k$ vertices and is its own E-subgraph, and since a triangle needs at least two paths, any path-decomposition of it needs at least $2k=\frac23|V(G)|$ paths (the print says "$3k$ vertex-disjoint triangles" but counts $|V(G)|=3k$ and $2k$ paths, which fit $k$ triangles; the ratio $\frac23$ holds either way). The introduction closes by announcing the Main theorem, $\lfloor\frac n2\rfloor$ paths whenever the E-subgraph can be obtained from the empty set by $\alpha$-operations, proved with Lovász's path sequence technique from [4].
• § 2, $\alpha$-operations and $\alpha$-graphs (pp. 118--120). Definition 2.1 (p. 118), restated: in a graph $H$, a pair $(S,y)$ with $S$ an independent set and $y\in S$ is an $\alpha$-pair when every vertex $v\in S\setminus\{y\}$ with $d_H(v)\ge2$ satisfies both (a) $d_H(u)\le3$ for every $u\in N_H(v)$ and (b) $d_H(u)=3$ for at most two $u\in N_H(v)$; the conditions bind only the vertices $v\ne y$ of $S$ of degree at least 2. An $\alpha$-operation on $H$ is either (i) the addition of an isolated vertex or (ii) the choice of an $\alpha$-pair $(S,y)$ and the addition of a new vertex $x$ adjacent to each vertex of $S$; in case (ii) the ordered triple $(x,S,y)$ is the $\alpha$-triple of the operation. Definition 2.2 (p. 119, quoted): "An $\alpha$-graph is a graph that can be obtained from the empty set via a sequence of $\alpha$-operations." The empty set is an $\alpha$-graph; a graph is an $\alpha$-graph iff its vertices have an $\alpha$-ordering $x_1x_2\ldots x_n$, each initial segment inducing an $\alpha$-graph obtained by an $\alpha$-operation from the previous one; "by the definition, an $\alpha$-graph is triangle-free" (p. 119). Proposition 2.3: "Any subgraph of an $\alpha$-graph is an $\alpha$-graph" (the restriction of an $\alpha$-ordering). Proposition 2.4: "Any subdivision of an $\alpha$-graph is an $\alpha$-graph" (insert the new vertices of a subdivided edge $xy$ just before $y$ in the ordering). Proposition 2.5: "Forests are $\alpha$-graphs" (remove a leaf $x$ with neighbor $y$; the $\alpha$-triple is $(x,\{y\},y)$). A circuit of length at least $4$ is an $\alpha$-graph, and more generally Proposition 2.6 (p. 119, quoted): "If each block of $G$ is a triangle-free graph of maximum degree at most 3, then $G$ is an $\alpha$-graph." Its proof (pp. 119--120), by induction on $|V(G)|$: in an end-block $B$ let $b$ be its cut vertex (any vertex if $B=G$), $x$ a neighbor of $b$ in $B$, $S=N_G(x)=N_B(x)$ and $H=G-x$; $S$ is independent since $B$ is triangle-free, and the degree bounds of Definition 2.1 hold for $v\in S\setminus\{b\}$ since $B$ has maximum degree at most $3$, so $G$ is obtained from $H$ by the $\alpha$-operation with $\alpha$-triple $(x,S,b)$.
• § 3, Technical lemmas (pp. 120--123). Definition 3.1: for a path-decomposition $\mathcal D$ of $G$, $\mathcal D(v)$ is the number of nontrivial paths of $\mathcal D$ with $v$ as an end; an odd-degree vertex has $\mathcal D(v)\ge1$. Definition 3.2: for a set $B$ of edges at a vertex $a$, $H=G\setminus B$ and a path-decomposition $\mathcal D$ of $H$, a set $A=\{ax_i:1\le i\le k\}\subseteq B$ is called addible at $a$ (relative to $\mathcal D$) when some path-decomposition $\mathcal D^*$ of $H\cup A$ has $|\mathcal D^*|=|\mathcal D|$, $\mathcal D^*(a)=\mathcal D(a)+|A|$, $\mathcal D^*(x_i)=\mathcal D(x_i)-1$ for each $i$ and $\mathcal D^*(v)=\mathcal D(v)$ at every other vertex; such a $\mathcal D^*$ is what the paper calls a transformation of $\mathcal D$ obtained by adding $A$ at $a$. Lemma 3.3 (p. 120), for $H=G\setminus\{ax_1,\ldots,ax_s\}$: either some $ax_i$ is addible at $a$, or $\sum_{i=1}^s\mathcal D(x_i)\le|\{v\in N_H(a):\mathcal D(v)=0\}|$; its proof (pp. 120--121) is Lovász's path sequence technique, following from each pair (end $x_i$, path $P$) the chain of paths through $a$ and showing the chains that end at a vertex $b_t$ with $\mathcal D(b_t)=0$ end at distinct vertices. Lemma 3.4 is the case $s=1$: if $\mathcal D(b)>|\{v\in N_H(a):\mathcal D(v)=0\}|$ then $ab$ is addible at $a$. Lemma 3.5 (pp. 121--122): if $\mathcal D(x_i)\ge1$ for all $i$, some $A\subseteq\{ax_1,\ldots,ax_s\}$ with $|A|\ge\lceil\frac{s-r}2\rceil$ is addible at $a$, $r=|\{v\in N_H(a):\mathcal D(v)=0\}|$. Lemma 3.6 (p. 122): if $\mathcal D(v)\ge1$ for all $v\in N_G(a)$, then for any $x\in\{x_1,\ldots,x_h\}$ some $B\ni ax$ with $|B|\ge\lceil\frac h2\rceil$ is addible at $a$. Lemma 3.7 (p. 122): for $H=G\setminus\{bx_1,\ldots,bx_k\}$, if $|\{v\in N_H(x_i):\mathcal D(v)=0\}|\le m$ for each $i$ and $\mathcal D(b)\ge k+m$, then $G$ has a path-decomposition of size $|\mathcal D|$ (adding the edges one at a time at the $x_i$ by Lemma 3.4). The paper notes (p. 120) that Lemmas 3.3 and 3.5 are special cases of Lemmas 4.3 and 4.6 of its [3], the 2002 covering paper, "whose proofs are rather complicated", and proves them afresh.
• § 4, Main theorem (pp. 123--125). Lemma 4.1 (p. 123, quoted): "Let $F$ be the E-subgraph of a graph $G$. For $a\in V(F)$ and $\{x_1,x_2,\ldots,x_s\}\subseteq N_F(a)$, where $s$ is odd and $d_F(x_i)\le3$, $2\le i\le s$, if $G\setminus\{ax_1,ax_2,\ldots,ax_s\}$ has a path decomposition $\mathcal D$ such that $\mathcal D(v)\ge1$ for all $v\in N_G(a)\cup\{a\}$, then $G$ has a path decomposition $\mathcal D^*$ with $|\mathcal D^*|=|\mathcal D|$." Its proof adds $t\ge\lceil\frac s2\rceil=k+1$ of the edges at $a$ by Lemma 3.6 ($s=2k+1$) and the remaining at most $k$ edges by Lemma 3.7 with $m=2$, since each remaining $x_i$ has at most two even-degree neighbors. Main theorem (p. 124, quoted): "Let $G$ be a graph on $n$ vertices (not necessarily connected). If the E-subgraph of $G$ is an $\alpha$-graph, then $G$ can be decomposed into $\lfloor\frac n2\rfloor$ paths." The proof (pp. 124--125) is summarized on the result page. Corollary (p. 125, quoted): "Let $G$ be a graph on $n$ vertices (not necessarily connected). If each block of the E-subgraph of $G$ is a triangle-free graph with maximum degree at most 3, then $G$ can be decomposed into $\lfloor\frac n2\rfloor$ paths", introduced as "a combination of Proposition 2.6 and the Main theorem". A filing observation, not a review verdict: the edgeless case $E(F)=\emptyset$ of the Main theorem's proof cites Pyber's forest result as "[Theorem 0, 4]" (p. 124), while the reference list's [4] is Lovász's paper; Pyber's 1996 paper, whose Theorem 0 it is, is [6], as the introduction (p. 118) and the opening of § 4 (p. 123) cite it.

Compiled scope

The paper is compiled at statement depth for the two results the citing problem consumes: the Corollary (p. 125) with Proposition 2.6 (p. 119), paged on corollary, and the Main theorem (p. 124) with Definitions 2.1--2.2 and Propositions 2.3--2.5, paged on main_theorem. The lemmas of § 3 and Lemma 4.1 are recorded as statements; the proofs were read as stated in the read status. Nothing here is independently reviewed.

Bears on. #583: the Corollary (printed p. 125, PDF p. 9), "Let $G$ be a graph on $n$ vertices (not necessarily connected). If each block of the E-subgraph of $G$ is a triangle-free graph with maximum degree at most 3, then $G$ can be decomposed into $\lfloor\frac n2\rfloor$ paths", is the block-condition row of that page's table, and the quotation as Theorem 1.2 of Bonamy and Perrett agrees with the printed statement. The Main theorem (printed p. 124, PDF p. 8), the table's $\alpha$-graph row, gives the same $\lfloor n/2\rfloor$ paths for the wider class of graphs whose E-subgraph is an $\alpha$-graph, which by Propositions 2.3--2.6 (p. 119) contains every forest, every subdivision and subgraph of an $\alpha$-graph, and every graph whose blocks are triangle-free of maximum degree at most $3$, and consists of triangle-free graphs; it strengthens Pyber's Theorem 0, which its proof invokes for the graphs whose E-subgraph has no edges. Both statements hold for every graph, connected or not, and give $\lfloor n/2\rfloor$ paths, one fewer than the conjecture's $\lceil n/2\rceil$ when $n$ is odd; the disjoint triangles of p. 118 show that the triangle-free requirement cannot be dropped and that no bound near $n/2$ holds for disconnected graphs without a restriction on the E-subgraph. Page 118 also states the consequence of Lovász's theorem for graphs with at most one vertex of even degree with $\lfloor n/2\rfloor$ paths, a floor where that page's Lovász row, taken from other second-hand quotations, has $\lceil n/2\rceil$. The paper states Gallai's conjecture with $\lceil n/2\rceil$ for connected graphs (p. 118) and does not settle it.

Results.

• Main theorem (p. 124; proof pp. 124--125): a graph on $n$ vertices whose E-subgraph is an $\alpha$-graph is decomposed into $\lfloor n/2\rfloor$ paths.
• Corollary (p. 125; from Proposition 2.6, p. 119, and the Main theorem): a graph on $n$ vertices each block of whose E-subgraph is a triangle-free graph of maximum degree at most $3$ is decomposed into $\lfloor n/2\rfloor$ paths.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.