2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – quasi Apr 11 at 2:10
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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". $\endgroup$ – Misha Lavrov Apr 11 at 3:15
  • $\begingroup$ I take your point regarding an intro graph theory class. But your analogy to real analysis is not really apt. The extended reals are more of a notational convenience than anything else. As one gets beyond introductory graph theory, infinite graphs become an increasingly important part of the entire picture of graph theory. And they are very important in applications of graphs. $\endgroup$ – Lee Mosher Apr 11 at 13:43
  • $\begingroup$ Perhaps a better analogy would be to directed graphs. Those are also an important part of the entire picture of graph theory - to some people. At the same time, I've certainly read, and probably written, research papers whose main result would be nonsense if you allowed infinite graphs or directed graphs. I don't think those researchers are at fault for not mentioning that the graphs in question are finite and undirected. $\endgroup$ – Misha Lavrov Apr 11 at 13:49

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.