Worked solution: A rainbow-tree proof of Ringel's conjecture (2020)

Step 3 of 8: Splitting trees into three shapes to attack separately

In plain words

Trees can look wildly different -- a star with $n$ leaves, a long thin path, or something in between -- so no single technique handles them all. The authors show that every large enough tree $T$ falls into (at least) one of three convenient shapes: plenty of separated leaves to trim off (Case A), plenty of long thin "bare" stretches to work with (Case B), or, failing both, a tree so dominated by a few very high-degree vertices that trimming their leaves collapses it to something tiny (Case C).

T \text{ has at least } \delta^6 n \text{ non-neighbouring leaves}

Detailed analysis

Montgomery, Pokrovskiy and Sudakov (2021, Section 2, Lemma 3.5 "Case division") show that for a small constant $\delta > 0$ , every sufficiently large $(n+1)$ -vertex tree falls into at least one of three cases: Case A, $T \text{ has at least } \delta^6 n \text{ non-neighbouring leaves}$ , where a leaf is called non-neighbouring if it is not adjacent to another leaf; Case B, $T \text{ has at least } \delta n/800 \text{ vertex-disjoint bare paths of length } \delta^{-1}$ , where a bare path is one whose internal vertices all have degree $2$ in $T$ ; and Case C, $\text{removing leaves next to vertices of degree} \ge \delta^{-4} \text{ leaves a tree with at most } n/100 \text{ vertices}$ . The three cases overlap, but the paper only ever needs to treat a tree as belonging to Case A or B (if it does), or else Case C.

Terms in this step

Leaf: A vertex of degree $1$ in a tree.
Bare path: A path inside $T$ all of whose internal vertices have degree exactly $2$ in $T$ (so the path is not interrupted by any branching).

Knowledge used in this step

Graphs, degree, and paths