4

Prove that every nontrivial tree has at least 2 vertices of degree 1 by showing that the origin and terminus of a longest path in a nontrivial tree both have degree 1.

Ok, so this statement is pretty obviously true, but I am having trouble proving it using graph theory language. What I have is that the origin and terminus must have degree 1 because if they had degree >=2, then they would not be the said origin and terminus but the vertex they are connected to would then be the origin or terminus. If that point has degree greater than or equal to 2 then the vertex that is connected to would be the origin or terminus and so on. Can someone help me put this into graph theory language, please.

Thanks

Brian
  • 711
  • 1
  • 10
  • 20

2 Answers2

4

You haven't actually used anything here that requires that you are discussing a tree; that should make you very suspicious! But, you've got just about the right idea.

Let $T$ be our tree, and $P=(p_0,p_1,\ldots,p_k)$ a path of longest length. Suppose that $p_0$ has degree strictly greater than $1$; let $v$ be a neighbor of $p_0$ other than $p_1$.

Consider two cases, and show that each is a contradiction:

Case 1: The vertex $v$ is not in the path $P$. Then you can extend the path to get $P'=(v,p_0,p_1,\ldots,p_k)$; this is a path of longer length, as you pointed out, which contradictions our assumption that $P$ is maximal.

Case 2: The vertex $v$ is already in the path. Here's where you're going to need to use the fact that $T$ is a tree to find a contradiction. Hint: Trees cannot contain cycles.

Nick Peterson
  • 32,430
0

I think the point which you are missing is, that all the edges incident to an endpoint $v$ of a longest path have also to be incident to another edge of the path. Otherwise, as you said, $v$ couldn't be the endpoint of a longest path. Hence if the degree of $v$ is $\geq 2$, the graph would have a circuit. But since it is a tree, this is impossible.

user130065
  • 136