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

Abstract An n -vertex graph is degree 3-critical if it has $$2n - 2$$ 2 n - 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 $$\Omega (\log n)$$ Ω ( log n ) distinct cycle lengths; every tree with maximum degree $$\Delta \ge 3$$ Δ ≥ 3 and $$\ell $$ ℓ leaves has at least $$\log _{\Delta -1}\, ((\Delta -2)\ell )$$ log Δ - 1 ( ( Δ - 2 ) ℓ ) distinct leaf-to-leaf path lengths; for every integer $$N\ge 1$$ N ≥ 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 , and, conversely, every 1–3 tree on at least $$2^N$$ 2 N vertices has $$\Omega (N^{2/3})$$ Ω ( N 2 / 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.