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

Abstract An n -vertex graph is degree 3-critical if it has $$2n - 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> distinct cycle lengths; every tree with maximum degree $$\Delta \ge 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> and $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> leaves has at least $$\log _{\Delta -1}\, ((\Delta -2)\ell )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>log</mml:mo> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mspace/> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>Δ</mml:mi> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> distinct leaf-to-leaf path lengths; for every integer $$N\ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , there exist arbitrarily large 1–3 trees which have $$O(N^{0.91})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>0.91</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> distinct leaf-to-leaf path lengths smaller than N , and, conversely, every 1–3 tree on at least $$2^N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>N</mml:mi> </mml:msup> </mml:math> vertices has $$\Omega (N^{2/3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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.