# Let T be a tree such that every leaf is adjacent to a vertex of degree at least 3. Show that there are two leaves with a common neighbor.

I came up with a proof for this but I think it might be a little hand-wavy and I can't figure out why. Some advice on how to make this proof clearer will be really appreciated!

Problem: Let $$T$$ be a tree such that every leaf is adjacent to a vertex of degree at least $$3$$. Show that there are two leaves with a common neighbor.

Proof: Suppose by contradiction that there are no two leaves with a common neighbor in T. Then let there be $$k$$ leaves in T and because each leaf is adjacent to a vertex of degree at least $$3$$, then there are k vertices in T that has degree at least $$3$$. For vertices other than the leaves and the leaves' neighbor, there are $$V(T)-2k$$ of those vertices and because they are not leaves they have degree of at least 2. So the minimum sum of degree of vertices in $$T$$ is $$\sum_{v\in T}d(v)=k+3k+2\cdot (V(T)-2k)=2V(T)$$ however by degree sum formula there is exactly $$\sum_{v\in T}d(v)=2V(T)-2$$, a contradiction.

• Note this entire theorem only works on finite trees. Otherwise the infinite path with one leaf hanging off each vertex is a counterexample. Feb 19, 2021 at 7:14
• Yeah, or simply an infinite tree which has no leaf ^^ Feb 19, 2021 at 10:48

If no two leafs have common neighbour, then when deleting all leafs we get a graph $$H$$ with all vertices of degree $$2$$ or more in $$H$$. So $$H$$ has a cycle. But then $$T$$ has also a cycle. A contradiction.
You could also root you tree anywhere and take a leaf of maximal depth $$\delta$$. Since its parent (of depth $$\delta - 1$$) is of degree 3, there is another node of depth $$\delta$$, and it is a leaf (because there is no node of depth $$\delta + 1$$).
Proof: Let a graph $$G$$ be a tree on $$n$$ vertices with $$\ell$$ leaf nodes and $$h$$ vertices of degree $$3$$ or more. Then $$G$$ has $$n{-}1$$ edges and by handshaking we know:
$$2(n-1) = \sum d(v_i) \; \geq \; \ell + 2(n-\ell-h) + 3h = 2n-\ell+h,\quad$$ so $$\ell-2\geq h$$ as required.
Now since in your question every leaf in $$T$$ is attached to a degree-$$3+$$ node, by the pigeonhole principle some leaves must be attached to the same such node.