What would be an elegant way to prove that every tree with at least two vertices contains a young parent?
I was thinking of using induction, with a base case of n = 2 (n is the number of vertices) and an assumption : it's true for n = p
But then I struggle making the proof in a mathematical way. Yet, I can see how is it true using a graphic representation of a graph.
Suppose that the result is false. Among all counterexamples let $T$ be a tree with the smallest possible number of vertices; clearly $T$ has more than $2$ vertices. Let $v$ be a leaf of $T$, and let $T'$ be the tree that remains after $v$ is removed from $T$. $T'$ has at least $2$ vertices and fewer vertices than $T$, so $T'$ has a young parent $u$, and it’s easy to verify that $u$ is a young parent in $T$ as well. This contradiction shows that there cannot be any counterexamples.