Tree with 3-degree vertices adjacent to leaves

427 Views Asked by At

Let $T$ be a tree such that all vertices adjacent to a leaf have degree at least 3. Prove that $T$ has two leaves adjacent to a common vertex.

1

There are 1 best solutions below

0
On

Let $P = (u, v, z, \dots)$ be a maximum path on $T$. We have that $d(u) = 1$, otherwise we would be able to define a greater path through $u$'s adjacencies. Moreover, $d(v) \geq 3$, because $v$ is adjacent to a leaf.

Let $x \in V(T)$ such that $xv \in E(T)$, $x \not = u$, and $x \not = z$. Since $T$ is a tree then $x$ cannot lie on $P$ (otherwise we would have a cycle). Hence, $d(x) = 1$ and $x$ is a leaf (if $x$ is not a leaf then we would be able to define a greater path than $P$ through $x$'s adjacencies).

So, $u$ and $x$ are leaves adjacent to the same vertex $v$.