Lagmental Vicfred

Every Nontrivial Tree Has at Least Two Leaves by Vicfred

The endpoints of a longest path in a finite tree must have degree one. The point is to make the formal expression readable enough to audit line by line.

Definitions first

A finite graph \(T=(V,E)\) is a tree when it is connected and acyclic. The unique simple path \(P_{uv}\) between two vertices makes distance and recursive decomposition especially rigid.

$$ |V(T)|\ge2 $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ \#\{v:\deg(v)=1\}\ge2 $$

A small case in full

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ v_0v_1\cdots v_k\ \text{longest}\Longrightarrow\begin{cases}\deg(v_0)=1,\\\deg(v_k)=1,\end{cases}\quad\text{or the path could be extended} $$

The reusable statement

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad |V(T)|\ge2,\\[5pt] \mathsf{C}\;&:\quad \#\{v:\deg(v)=1\}\ge2. \end{aligned} $$

A nearby false statement

A rooted tree adds a parent relation that an unrooted tree does not possess. Statements about ancestors depend on the chosen root.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \#\{v:\deg(v)=1\}\ge2 \end{gathered}} $$

The final box is a summary, not a new assumption; the proof still lives in the definitions and the intervening calculation. The source keeps each scope delimiter visible for later inspection.

This article was posted on Tue 23 May 2023. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.