3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Either saying what you have already said is fine or construct some argument like, assume $d(v)$ is greater than $2$ and show that that is not a path. $\endgroup$ – stuart stevenson Jan 7 '18 at 2:52
1
$\begingroup$

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:

enter image description here

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.