Prove that T (tree) is a path iff $d(v) = 2$

Question

Let $T$ be a tree with n vertices, $n \geq 4$, and $v$ is a vertex with maximum degree in $T$. Prove that $T$ is a path iff $d(v) = 2$.

My attempt: Logically, if a vertex has maximum degree more than $2$, then the tree will contain branches (no cycle of course) and that's why it is not a path then. In generalization, $(v_0, v_1, \cdots, v_i, \cdots, v_n)$ where $v_i$ has more than degree $2$, then we can't found a single last vertex $v_n$ (branches).

Somehow I think that we should use induction. But I myself can't proceed. So, do you have any idea? Regards. Sorry for my bad English.

Answer 1

Notice that this is an if and only if statement, therefore we have two things to prove:

• If $T$ is a path, then $d(v) = 2$.
• if $d(v) = 2$ then $T$ is a path.

In your attempt, what you proved is the first argument (you assumed $T$ is a path and got a contradiction when you assumed $d(v)>2$. Obviously, $d(v) < 2$ is not possible with the constraint $n \ge 4$ so $d(v) = 2$). Induction is a nice way to prove the second argument. First of all, let $T_n$ be a tree with $n$ vertices and with maximum degree of a vertex $2$, where $n \ge 4$. For $n = 4$, there are only two possibilities for $T_4$ up to isomorphism as shown:

Since the second figure has a vertex with degree $3$, the first graph is $T_4$ and it is a path obviously. Now, suppose $n \ge 5$ and the argument holds for all $n$. Then in order to construct $T_{n+1}$ we need to add one more vertex to $T_n$. Since our conditions is not having a vertex with degree more than $2$, there are only two options where the last vertex can be added, namely the beginning and the ending of the path of $T_n$ (because otherwise, $T_{n+1}$ will have a vertex with degree $3$). But wherever we add the last vertex, either that vertex will be the beginning of the path of $T_{n+1}$ or the ending of the path, therefore, will construct a new path $T_{n+1}$. So $T_{n+1}$ is also a path and by induction, the argument holds for all $n$.

Answer 2

More generally, a (finite) tree with every vertex degree $\le2$ is a path. Every finite tree with at least two vertices has a leaf (vertex of degree one). Remove this and its incident edge and argue by induction.