2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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}$? $\endgroup$ Mar 6, 2014 at 4:39
  • $\begingroup$ @user112790, why not make that an answer? $\endgroup$
    – Casteels
    Mar 6, 2014 at 8:59
  • $\begingroup$ @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. $\endgroup$ Mar 6, 2014 at 15:46
  • $\begingroup$ @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. $\endgroup$
    – Casteels
    Mar 6, 2014 at 19:10

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ What did you mean by "...it has at most neighbor in $T'$...?" $\endgroup$
    – Mailbox
    Mar 13 at 18:02
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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