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.

combinatoricsdiscrete mathematicsgraph theorysolution-verificationtrees

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.

Best Answer

Suppose tree is finite.

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.

Related Question