# Proving a cut vertex in a tree, $T$, is an end-vertex:

If $T$ is a tree of order at least $3$, then $T$ contains a cut vertex $v$ such that every vertex adjacent to $v$, with at most one exception is an end vertex.

I know that if $T$ is a connected graph of order $3$ or more and it contains a bridge, then $T$ has a cut vertex. But I'm not sure how to apply it to this problem.

• HINT: Think about the longest path $P=v_0,v_1,\ldots,v_{n-1},v_n$. The vertices $v_0$ and $v_n$ both have to be end vertices of $T$, so what can you say about $v_1$ and $v_{n-1}$? Mar 6, 2014 at 4:39
• @user112790, why not make that an answer? Mar 6, 2014 at 8:59
• @Casteels: Because there are a few details that will need to be filled in justifying that either $v_1$ or $v_{n-1}$ is the vertex that we want. I am trying not to answer other people's homework for them. Mar 6, 2014 at 15:46
• @user112790, You don't need to fill in any details; hints are perfectly acceptable as "answers" in my opinion and, I'm sure, in many others' as well. Of course it's your choice. Mar 6, 2014 at 19:10

Since $T$ has order $n \geq 3$ the average degree of $T$ equals $\frac{2(n-1)}{n} > 1$. It follows that not every vertex of $T$ is a leaf (an end vertex). Consider the tree $T'$ which we get by removing all leaves from $T$. Since $T'$ is a tree, it has some leaf $v$. This vertex has the right property, as it has at most neighbor in $T'$ and every other neighbor it might have in $T$ is a leaf. Furtermore, $v$ is a cut vertex because it is not a leaf of $T$.
• What did you mean by "...it has at most neighbor in $T'$...?" Mar 13 at 18:02
Let $P=v_0,v_1,\ldots,v_{n-1},v_n$ be a longest path in $T$. Clearly $v_0$ must be an end vertex of $T$, otherwise we could extend $P$ to a longer path $P'$, which impossible.
Now consider $v_1$. Clearly $v_1$ is a cut vertex. Now there may be other vertices adjacent to it, but they would have to all be end vertices as well, otherwise we could extend $P$ to a longer path, which is impossible. If $P$ terminates at $v_2$, then $v_1$ is adjacent to all end vertices, otherwise $v_2$ is the one non-end vertex adjacent to $v_1$.