Trees-related proof

Question

I just began my Graph Theory course, so I'm pretty knew in this area, at least when it's about formal proofs(I have some experience on intuitive level, implementing certain algorithms related to graph theory such as shortest paths, MST, SCC etc.). Just bumped into some problems related to trees, such as this one: Prove that in any tree, with exactly 2 vertices of degree 3, there exist at least 4 leafs(vertices of degree 1). I suppose it's something basic, that requires usage of handshaking lemma or similar, but as I just began I'm not so sure. Anyone has a clue how to approach similar problems? Thanks!

Answer 1

Recall that in a tree, there are no cycles. If a path goes in one direction, it can never come back, and it has to terminate in a leaf eventually.

If vertices $v$ and $u$ have degree 3, consider the case where they are adjacent. Then $v$ and $u$ both have two other adjacent vertices, and paths from these vertices away from $v$ and $u$ eventually end in leaves.

If $v$ and $u$ are not adjacent, the same argument applies. There is exactly one path between $v$ and $u$, meaning there are 4 paths leading away from $v$ and $u$.

Answer 2

Hint: Let $T$ be our tree and let $a,b \in V(T)$ be the two vertices of degree three. Now consider what happens when we remove the unique $(a,b)$-path in $T$.