# Let $G$ be a graph other than the trivial one, with exactly one vertex of degree 1. Show that $G$ cannot be a tree.

Let $$G$$ be a graph other than the trivial one, with exactly one vertex of degree 1. Show that $$G$$ cannot be a tree.

Proof. Since we know that every tree has $$n-1$$ edges, then the total degree of any tree must be $$2 (n-1)$$. Then there are $$(n-1)$$ vertices with degree $$\geq 2$$ while only one vertex of degree 1. Thus, adding to find the total of the vertices, we have that the total degree of the vertices is $$\geq 2 (n-1) + 1 = 2n-1$$, which is a contradiction. Therefore $$G$$ is not a tree. $$\square$$

It's okay?

• I would also mention that $G$ can't have any vertices of degree $0$, else $G$ would be disconnected, whereas a tree must be connected. Other than that, your proof looks good. – quasi Apr 11 at 2:10

First, the statement itself is flawed in that there is a hidden hypothesis that should be made explicit: the tree is assumed to be finite. The statement is false if you allow for infinite trees (there is, in fact, an infinite tree having exactly one vertex of degree $$1$$).
Second, the quantity $$n$$ has not been defined. I can see from later steps that $$n$$ is the number of vertices, but this should be stated right at the beginning of the proof.
Finally, in a formal proof you would give a citation for what you already know, in this case the theorem that if a tree has $$n$$ vertices then it has $$n-1$$ edges.
• Assuming graphs to be finite is not "a hidden hypothesis that should be made explicit". Most people work with finite graphs only (especially in an intro graph theory class). That's like approaching a real analysis problem and saying "a hidden hypothesis is that we are not considering the extended reals, so $\infty$ is not a number". – Misha Lavrov Apr 11 at 3:15