Leaf-to-leaf paths and cycles in degree-critical graphs
Francesco Di Braccio, Kyriakos Katsamaktsis, Jie Ma, Alexandru Malekshahian, Ziyuan Zhao · 2025
Read Leaf-to-leaf paths and cycles in degree-critical graphs by Francesco Di Braccio, Kyriakos Katsamaktsis, Jie Ma, Alexandru Malekshahian, Ziyuan Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-11656.txt.
Introduction
Di Braccio, Katsamaktsis, Ma, Malekshahian, and Zhao resolve questions on leaf-to-leaf paths and cycles in degree-critical graphs, in a paper from twenty twenty-five. Degree three-critical graphs have tight edge counts with no dense induced subgraphs. A nineteen eighty-eight question on short cycle lengths was disproven via tree constructions. Weaker conjectures on cycle and path length diversity remained open.
Every such graph has logarithmically many distinct cycle lengths. Trees with many leaves guarantee many distinct leaf-to-leaf path lengths logarithmically. Large one-three trees split both ways around a threshold length. Some have few short path lengths, while huge ones must have many. Additive combinatorics powers several of the proofs.
Catalog record
| CREATOR | Francesco Di Braccio, Kyriakos Katsamaktsis, Jie Ma, Alexandru Malekshahian, Ziyuan Zhao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-11656
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Leaf-to-leaf paths and cycles in degree-critical graphs Francesco Di Braccio, Kyriakos Katsamaktsis, Jie Ma, Alexandru Malekshahian, Ziyuan Zhao Abstract An n n -vertex graph is degree 3-critical if it has 2 n − 2 2n-2 edges and no proper induced subgraph with minimum degree at least 3. In 1988, Erdős, Faudree, Gyárfás, and Schelp asked whether one can always find cycles of all short lengths in these graphs, which was disproven by Narins, Pokrovskiy, and Szabó through a construction based on leaf-to-leaf paths in trees whose vertices have degree either 1 or 3. They went on to suggest several weaker conjectures about cycle lengths in degree 3-critical graphs and leaf-to-leaf path lengths in these so-called 1-3 trees. We resolve three of their questions either fully or up to a constant factor. Our main results are the following: • every n n -vertex degree 3-critical graph has Ω ( log n ) \Omega(\log n) distinct cycle lengths; • every tree with maximum degree Δ ≥ 3 \Delta\geq 3 and ℓ \ell leaves has at least log Δ − 1 ( ( Δ − 2 ) ℓ ) \log_{\Delta-1}\,((\Delta-2)\ell) distinct leaf-to-leaf path lengths; • for every integer N ≥ 1 N\geq 1 , there exist arbitrarily large 1–3 trees which have O ( N 0.91 ) O(N^{0.91}) distinct leaf-to-leaf path lengths smaller than N N , and, conversely, every 1–3 tree on at least 2 N 2^{N} vertices has Ω ( N 2 / 3 ) \Omega(N^{2/3}) distinct leaf-to-leaf path lengths smaller than N N . Several of our proofs rely on purely combinatorial means, while others exploit a connection to an additive problem that might be of independent interest. 1 Introduction There is a long line of research in combinatorics seeking to understand what conditions guarantee that a graph contains cycles of many different lengths. In 1973, Bondy [ 5 ] made the famous meta-conjecture that any non-trivial condition that guarantees Hamiltonicity is enough to ensure that the n -vertex graph is pancyclic , i.e. that it contains all cycle lengths in \{3,\dots,n\} . This led to a host of interesting results in the following fifty years bringing support to Bondy’s conjecture in a variety of different settings [ 17 , 9 , 5 , 1 , 6 ] . However, most of the results in the area concern (somewhat) dense graphs, and for very sparse graphs our understanding of which graphs contain many cycle lengths is more fragmentary. Sudakov and Verstraëte [ 22 ] showed that graphs with average degree d and girth at least g contain \Omega(d^{\lfloor(g-1)/2\rfloor}) distinct cycles lengths, thus proving a conjecture of Erdős [ 13 ] . A related conjecture of Erdős and Hajnal [ 13 ] was resolved by Gyárfás, Komlós, and Szemerédi [ 14 ] , who proved that in a graph with average degree d , the sum of the reciprocals of the distinct cycle lengths is \Omega(\log d) . The starting point of the present work is a conjecture of Erdős, Faudree, Gyárfás, and Schelp [ 10 ] , who asked whether many cycle lengths can be found in a specific class of sparse graphs called degree 3-critical graphs . These are defined to be graphs with n vertices, 2n-2 edges and no proper induced subgraph with minimum degree at least 3; it is not hard to see that these graphs necessarily have minimum degree 3. Degree 3-critical graphs satisfy several interesting properties; for example, they have no proper induced subgraph H on 2|V(H)|-2 edges, and hence, by a theorem of Nash-Williams [ 19 ] , they are the union of two edge-disjoint spanning trees. Erdős, Faudree, Gyárfás, and Schelp [ 10 ] proved that any n -vertex degree 3-critical graph contains a cycle of length 3, 4, and 5, as well as a cycle of length at least \log n . 1 1 1 Unless indicated otherwise, logarithms throughout this paper are base 2. This last bound was later improved by Bollobás and Brightwell [ 2 ] to 4\log n+O(\log\log n) , which is asymptotically best possible. In an effort to reveal a rich structure of cycle lengths in such graphs, Erdős et al. [ 10 ] (also see [ 12 ] ) conjectured that it should be possible to find cycle lengths 3,4,5\dots,N for some N=N(n)\to\infty as n\to\infty . Their conjecture, however, was disproven by Narins, Pokrovskiy, and Szabó [ 18 ] who showed that there are arbitrarily large degree 3-critical graphs with no cycle of length 23. The crucial ingredient of their construction is a particular class of trees called 1–3 trees . A 1–3 tree is a tree where every vertex has degree either 1 or 3. It was shown in [ 18 ] that there exist infinitely many 1–3 trees with no two leaves at distance 20 from one another, which then yielded the desired degree 3-critical graphs by adding two vertices adjacent to all leaves and to each other. Despite their surprising counterexamples, the authors of [ 18 ] proved that any degree 3-critical graph with at least six vertices contains a cycle of length 6, and asked whether it might still be the case that degree 3-critical graphs contain many cycle lengths. They posed the following conjecture. Conjecture A ( [ 18 , Conjecture 6.2] ) . Every degree 3-critical graph on n vertices contains cycles of at least 3\log n+O(1) distinct lengths. A classical construction of Bollobás and Brightwell [ 2 ] shows that, if true, Conjecture A is best possible. Our first result proves that Conjecture A is true up to a constant factor. Theorem 1 . Every degree 3-critical graph on n vertices contains cycles of at least \frac{\log n}{3+\log 3}+O(1) distinct lengths. This provides the first bound on the number of cycle lengths as a function of n tending to infinity, and arguably can be viewed as confirmation of the original motivation of Erdős et al. [ 10 ] to demonstrate the abundance of cycle lengths in such graphs. In fact, we establish this result as a corollary of a more general theorem (Theorem 12 ) which applies to degree k -critical graphs for any k\geq 3 , i.e., n -vertex graphs with (k-1)n-\binom{k}{2}+1 edges and no proper induced subgraph with minimum degree at least k . This family was introduced by Bollobás and Brightwell [ 2 ] as a natural generalization of degree 3-critical graphs, and a problem closely related to this family was studied more recently by Sauermann [ 21 ] . The key idea behind the proof of Theorem 1 is to define an appropriate partial ordering on the vertex set of the given graph. By Dilworth’s theorem, this either gives a long chain or a long antichain. The first case yields a long path P together with a collection of paths that intersect P in a special way (a structure known as a vine ). In the second case, we find two large trees that are vertex-disjoint except for the fact that they share the same set of leaves. A careful analysis then yields many cycle lengths in either case. Motivated by the connection between degree 3-critical graphs and 1–3