Leaf-to-leaf paths and cycles in degree-critical graphs

Journal article

An n-vertex graph is degree 3-critical if it has 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-vertex degree 3-critical graph has Ω(logn) distinct cycle lengths; every tree with maximum degree Δ≥3 and ℓ leaves has at least logΔ-1((Δ-2)ℓ) distinct leaf-to-leaf path lengths; for every integer N≥1, there exist arbitrarily large 1–3 trees which have O(N0.91) distinct leaf-to-leaf path lengths smaller than N, and, conversely, every 1–3 tree on at least 2N vertices has Ω(N2/3) distinct leaf-to-leaf path lengths smaller than 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.

Authors: Braccio, FD; Katsamaktsis, K; Ma, J; Malekshahian, A; Zhao, Z

• Alternative title: Leaf-to-leaf paths and cycles in degree-critical graphs
• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Combinatorica
• Volume: 46
• Issue: 2
• Article number: 11
• Publication date: 2026-03-04
• Acceptance date: 2026-01-28
• DOI: 10.1007/s00493-026-00205-2
• EISSN: 1439-6912
• ISSN: 0209-9683
• Language: English