Pyber 1996 covering edges connected graph paths

../

theorem_0: Pyber's forest case of Gallai's conjecture: a graph on n vertices in which every cycle contains a vertex of odd degree, that is, whose even-degree vertices induce a forest, is covered by floor(n/2) edge-disjoint paths, and K_{2m+1} minus m-1 independent edges, an odd semi-clique, shows the theorem is best possible.

theorem_i: Pyber's covering theorem: every connected graph on n vertices is covered by n/2 + O(n^(3/4)) paths that may share edges, the asymptotic form of Gallai's conjecture for coverings, with Theorem II's n/2 + 4e/n paths for a graph with e edges.

theorem_ii: Pyber's edge-count covering bound: every connected graph on n vertices with e edges is covered by n/2 + 4(e/n) paths that may share edges, stronger than Theorem I when the graph has few edges.

---

L. Pyber, Covering the Edges of a Connected Graph by Paths, J. Combin. Theory Ser. B 66 (1996), 152--159, article no. 0012, DOI 10.1006/jctb.1996.0012 (the DOI is the publisher's record; the header prints "Journal of Combinatorial Theory, Series B 66, 152--159 (1996)" over "Article No. 0012" and the copyright line "1996 by Academic Press, Inc."); received September 11, 1991 (p. 152); the author at the Mathematical Institute, Hungarian Academy of Sciences, Budapest, with research partially supported by a Hungarian National Foundation for Scientific Research grant (footnote, p. 152). Cited as [Py96] on the problem page. Its thirteen references (p. 159): [1] Chung, On the coverings of graphs, Discrete Math. 30 (1980), 89--93, a different paper from the tree-partition paper the problem page cites as [Ch78]; [2] Donald, An upper bound for the path number of a graph, J. Graph Theory 4 (1980), 189--201; [3] Erdős and Gallai, On maximal paths and circuits of graphs (1959), filed as erdos_1959_maximal_paths_circuits_graphs; [4] Häggkvist and Thomassen, Circuits through specified edges, Discrete Math. 39 (1982), 59--65; [5] Jørgensen, Coverings of infinite graphs, Ars Combin. 29C (1990), 157--159; [6] Jørgensen and Pyber, Covering a graph by topological complete subgraphs, Graphs Combin. 6 (1990), 167--171; [7] Li, Perfect path double covers in every simple graph, J. Graph Theory 14 (1990), 645--650; [8] Lovász, On covering of graphs, in Theory of Graphs, Proc. Coll. Tihany, 1966 (1968), 231--236, the problem page's [Lo68], not held; [9] Pyber, An Erdős--Gallai conjecture, Combinatorica 5 (1985), 67--79, the [Py85] of Problem 184, not held; [10] Pyber, Covering the edges of a graph by ..., in Sets, Graphs and Numbers, Proc. Colloq. Budapest, 1991, Colloq. Math. Soc. János Bolyai 60 (1992), 583--610; [11] Rado, A theorem on independence relations, Quart. J. Math. Oxford 13 (1942), 83--89; [12] Thomason, Hamiltonian cycles and uniquely edge-colourable graphs, in Advances in Graph Theory (1978), 259--268; [13] Welsh, Matroid Theory (1976). Only [3] has a card here.

The copy read for this card is the publisher's production PDF of the printed article: 8 pages, printed pp. 152--159 = PDF pp. 1--8 (printed p. $n$ is PDF p. $n-151$), typeset pages 356 points wide and 576 high, the first 598 high (the file's metadata names Acrobat Distiller 2.0 for Macintosh and a creation date of 8 January 1996, modified in April 2015), each with a typesetter's stamp in the left margin, and a text layer that reads the prose cleanly and garbles floors, ceilings, fractions, subscripts and set operations ($\lfloor n/2\rfloor$ comes out as "wn2x", $n/2+O(n^{3/4})$ as "n2+O(n 34 )"), so every statement below was checked on the page image. Provenance: the copy read was downloaded on 2026-09-22 from the publisher's open archive, the DOI https://doi.org/10.1006/jctb.1996.0012 resolving to the article's page (PII S009589569690012X), whose PDF is served free under the publisher's open-archive user license; 272,512 bytes. The file prints "Copyright © 1996 by Academic Press, Inc." and "All rights of reproduction in any form reserved." on its first page, every other right reserved.

Read status: all eight page images were read. Claims checked for the abstract, Lovász's theorem and corollary, Donald's bound and Theorem 0 (p. 152), the two Examples, Gallai's Conjecture as the paper states it, and Theorems I and II (p. 153), Lemma 1.1 (p. 154), Corollary 1.2, the sentence deriving Theorem 0, Corollary 1.3 and Lemma 1.4 (p. 155), Lemma 1.5 and Lemma 2.1 (p. 156) and the three theorems of § 3 (pp. 158--159), each read clause by clause on the page images. The proofs of Corollary 1.2 (three lines, p. 155) and of Theorem 0 (one sentence, p. 155) were read in full and followed; the proof of Theorem I (p. 157) was read in full on the page image and its steps were followed as summarized on the result page, with the arithmetic not checked; the proofs of Lemma 1.1 (pp. 154--155), Lemma 1.4 (pp. 155--156), Lemma 2.1 (pp. 156--157) and Theorem II (pp. 157--158) were read for structure only. Nothing here is independently reviewed.

Contents

• Abstract and Introduction (pp. 152--153). The abstract announces the covering bound of Theorem I, at most $n/2+O(n^{3/4})$ paths for every connected graph on $n$ vertices, and reads it as the asymptotic truth of a weak form of Gallai's conjecture. Lovász's theorem (p. 152), quoted: "Every graph $G$ on $n$ vertices can be covered by $\le\lfloor n/2\rfloor$ edge-disjoint paths and cycles." The paper recalls that the Erdős--Gallai conjecture, $O(n)$ edge-disjoint cycles and edges cover the edges of $G$, is still open, with [10] cited for details, while without edge-disjointness "by a result of the author [9], $n-1$ cycles and edges suffice" (p. 152; the statement Problem 184 records from second-hand sources). Corollary [8] (p. 152): "Let $G$ be a graph on $n$ vertices. (i) Then $G$ can be covered by $n-1$ edge-disjoint paths. (ii) If each vertex of $G$ has odd degree then $G$ can be covered by $n/2$ edge-disjoint paths." Donald [2] strengthened (i) to $\lfloor(3/4)n\rfloor$ edge-disjoint paths. Theorem 0 (p. 152, quoted): "Suppose that each cycle of $G$ contains a vertex of odd degree. Then $G$ can be covered by $\le\lfloor n/2\rfloor$ edge-disjoint paths." Example (p. 153): deleting $m-1$ independent edges from the complete graph $K_{2m+1}$ leaves a graph $G$ on $n=2m+1$ vertices with exactly $(n-1)\lfloor n/2\rfloor+1$ edges, so that $\lfloor n/2\rfloor+1$ paths are needed to cover it, while its only cycle with all degrees even is a triangle; the paper concludes that Theorem 0 is best possible. Then the Conjecture (p. 153, quoted): "Every connected graph $G$ on $n$ vertices can be covered by $\lfloor(n+1)/2\rfloor$ edge-disjoint paths." The paper calls this best possible, notes that strong partial results exist but a full proof looks very hard, and records that Chung [1] suggested the case of covering paths that need not be edge-disjoint. Theorem I (p. 153, quoted): "Every connected graph $G$ on $n$ vertices can be covered by $n/2+O(n^{3/4})$ paths." Theorem II (p. 153, quoted): "Every connected graph on $n$ vertices with $e$ edges can be covered by $n/2+4(e/n)$ paths." Example (p. 153), introduced with the remark (quoted) "It is curious to note that one cannot prove an asymptotic version of Gallai's conjecture without proving the conjecture itself": if $H$ is an $m$-vertex counterexample to the conjecture, so that every path partition of $H$ has at least $m/2+1$ paths, and the $n$-vertex graph $G$ is a vertex $v$ joined by one edge to each of $k$ vertex-disjoint copies of $H$, then partitioning $G$ takes at least $k(m/2+1)-\lfloor k/2\rfloor$ paths, which for $k\ge2m+3$ is at least $n/2+n/(2m+1)$, so no bound of the form $n/2+o(n)$ holds as $n\to\infty$.
• § 1, Edge-disjoint coverings (pp. 153--156). Lemma 1.1 (p. 154, quoted): "Let $\Sigma$ be a path and cycle partition of a graph $G$ with the number of cycles minimal among path and cycle partitions having at most $|\Sigma|$ elements. Let $C$ be a cycle of $\Sigma$ and $x$ an arbitrary vertex of $C$. There exist two vertices $y,z\in V(C)$ such that $(x,y),(x,z)\in E(G)$ and both $y$ and $z$ have even degree in $G$." Its proof "uses the method of Lovász [8]": from each $C$-neighbor of $x$ a sequence of $G$-neighbors of $x$ is traced through the paths of $\Sigma$ ending at odd vertices, and an exchange of $C$ and those paths for paths alone would reduce the number of cycles. Corollary 1.2 (p. 155, quoted): "Let $\Sigma$ be a cycle and path partition as in Lemma 1.1. Then for each cycle $C\in\Sigma$ there is a cycle $K$ of $G$ such that $V(K)\subseteq V(C)$ and the vertices of $K$ have even degree in $G$." Proof: the subgraph of $G$ induced by the even-degree vertices of $C$ has minimum degree at least two by Lemma 1.1. Then (p. 155) Theorem 0 follows at once from Corollary 1.2 and Lovász's theorem. Corollary 1.3 (p. 155, quoted): "Let $G$ be a $k$-connected graph on $n$ vertices. Then $G$ can be covered by $\lfloor n/2\rfloor+\lceil n/2k\rceil$ paths." Its proof removes a maximal matching $I$ between even-degree vertices, applies Theorem 0 to $G\setminus I$, and covers $I$ by $\lceil n/2k\rceil$ paths using Häggkvist and Thomassen's theorem that $k-1$ independent edges of a $k$-connected graph lie on a cycle. Lemma 1.4 (p. 155, quoted): "Let the graph $H$ be an edge-disjoint but not vertex-disjoint union of two cycles $C_1$ and $C_2$. Suppose $H$ cannot be covered by two paths. Then $C_1$ has an edge $e$ with both endvertices in $V(C_2)$." The proof uses Thomason's theorem that a Hamiltonian decomposition of a 4-regular multigraph is never unique. The paper adds (p. 156) that a much stronger form of this lemma would be the key to improving its results, and asks (quoted): "Perhaps it is possible to characterize pairs of edge-disjoint cycles $C_1$, $C_2$ that cannot be covered by two paths." Lemma 1.5 (p. 156): the same conclusion for a cycle $C$ and a path $P$, $C$ has an edge with both endvertices in $P$.
• § 2, The proofs of Theorems I and II (pp. 156--158). Lemma 2.1 (p. 156, quoted): "Let $G$ be a connected graph on $n$ vertices and let $x\le n$ be an even number. There exists a subgraph $R\subset G$ such that (i) any path $P$ of the graph $G\setminus R$ contains at most $x$ vertices that have even degree in $G\setminus R$ (ii) there is at most one vertex $w_0$ of even degree greater than $x^2$ in $G\setminus R$, and (iii) the edges of $R$ can be covered by $2(n/x)$ paths of $G$." Its proof strips paths through $x$ even vertices at a time and uses the Erdős--Gallai theorem [3] that $x\cdot n$ edges force a path of length $2x$. The proof of Theorem I (p. 157) is summarized on the result page. The proof of Theorem II (pp. 157--158) starts from a partition into exactly $\lceil n/2\rceil$ paths and cycles with the fewest cycles, calls an element long if it has at least $4e/n$ edges, exchanges pairs of a long cycle and a short element, then pairs of short cycles, whose union two paths cover, and finishes with Lemmas 1.4 and 1.5 on a short element $S$ with $|V(S)|\le4(e/n)+1$.
• § 3, Infinite graphs (pp. 158--159). Lovász's extension of Corollary (ii) to locally finite graphs with all degrees odd; Rado's theorem on independent transversals in a matroid; and the Theorem (p. 159, quoted): "Let $G$ be a finite graph. Then $G$ has a covering $\mathcal P$ by edge-disjoint paths such that $\mathcal P$ has a cycle-free transversal", proved from a minimal covering and Rado's theorem, with the question of its extension to infinite graphs.

Compiled scope

The paper is compiled at statement depth for the three results the citing problem consumes: Theorem 0 (p. 152) with its Example (p. 153) and its derivation (p. 155), paged on theorem_0, Theorem I (p. 153) with the second Example, paged on theorem_i, and Theorem II (p. 153), paged on theorem_ii. The lemmas and Corollary 1.3 are recorded as statements read on the page images; the proofs were read as stated in the read status. Nothing here is independently reviewed.

Bears on. #583: Theorem 0 (printed p. 152, PDF p. 1), quoted above, $\lfloor n/2\rfloor$ edge-disjoint paths when every cycle of $G$ has a vertex of odd degree, is the forest case that page's table attributes to the paper: a cycle of $G$ all of whose vertices have even degree is exactly a cycle of the subgraph induced by the even-degree vertices, so the hypothesis says that subgraph is a forest, and the quotation as Theorem 1.1 of Bonamy and Perrett agrees with the printed statement. The theorem is stated for every graph, connected or not, and gives $\lfloor n/2\rfloor$ paths, one fewer than the conjecture's $\lceil n/2\rceil$ when $n$ is odd; the Example of p. 153, the complete graph on $2m+1$ vertices minus $m-1$ independent edges, needs $\lfloor n/2\rfloor+1$ paths and has a triangle of even-degree vertices, so the floor cannot survive one even cycle; these graphs are odd semi-cliques in the sense of Bonamy and Perrett's Question 1.1. Theorem I (printed p. 153, PDF p. 2), quoted above, $n/2+O(n^{3/4})$ covering paths for every connected graph on $n$ vertices, is the covering bound the site records for the paper; the paths may share edges, so it does not bound the path number of the problem, and the paper's second Example (p. 153) shows why no such asymptotic statement can be proved for edge-disjoint paths short of the conjecture itself: one $m$-vertex counterexample yields connected graphs needing $n/2+n/(2m+1)$ paths. The paper states the conjecture as $\lfloor(n+1)/2\rfloor$ edge-disjoint paths (p. 153), the form of Erdős's 1971 question, and calls it Gallai's. Theorem II (printed p. 153), $n/2+4(e/n)$ covering paths for a connected graph with $e$ edges, is the second covering bound that page records; its paths may also share edges, so it does not bound the path number either. The paper does not settle the problem.

Results.

• Theorem 0 (p. 152; derived p. 155 from Corollary 1.2 and Lovász's theorem): a graph in which every cycle contains a vertex of odd degree is covered by $\lfloor n/2\rfloor$ edge-disjoint paths; sharp by the Example of p. 153.
• Theorem I (p. 153; proof p. 157): every connected graph on $n$ vertices is covered by $n/2+O(n^{3/4})$ paths that may share edges; the second Example of p. 153 shows that its edge-disjoint analogue cannot be proved without the conjecture itself.
• Theorem II (p. 153; proof pp. 157--158): every connected graph on $n$ vertices with $e$ edges is covered by $n/2+4(e/n)$ paths that may share edges.

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