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

145 Views Asked by At

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?

1

There are 1 best solutions below

3
On

It looks pretty good, I like the argument. But there are one or two stylistic things that you can do to improve the presentation of the statement and the proof.

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.