6
$\begingroup$

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.

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

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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$).

$\endgroup$
0
$\begingroup$

Lemma: Any tree has more leaf nodes than degree-3 and higher nodes.
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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .