5
$\begingroup$

Can someone please verify this?

Show that a connected graph on $n$ vertices is a tree if and only if it has $n-1$ edges.

$(\Rightarrow)$ If a tree $G$ has only $1$ vertex, it has $0$ edges. Now, assume that any tree with $k-1$ vertices has $k-2$ edges. Let $T$ be a tree with $k$ vertices. Remove a leaf $l$ to obtain a tree $T'$ with $k-1$ vertices. Then, $T'$ has $k-2$ edges, by the inductive hypothesis. The addition of $l$ to $T'$ produces a graph with $k-1$ edges, since $l$ has degree $1$.

$(\Leftarrow)$ Let $G$ be a connected graph on $n$ vertices, with $n-1$ edges. Suppose $G$ is not a tree. Then, there exists at least one cycle in $G$. Successively remove edges from cycles in $G$ to obtain a graph $G'$ with no cycles. Then, $G'$ is connected and has no cycles. Therefore, $G'$ is a tree, with $n$ vertices and $n-1-x$ edges, for some $x > 0$. However, this contradicts the previous derivation. Therefore, it must be the case that $G$ is a tree.

$\endgroup$
  • $\begingroup$ it seems to be true. $\endgroup$ – mesel Jun 15 '14 at 12:40
5
$\begingroup$

The proofs are correct. Here's alternative proof that a connected graph with n vertices and n-1 edges must be a tree modified from yours but without having to rely on the first derivation:

Let $G$ be a connected graph on n vertices, with n−1 edges. Suppose $G$ is not a tree. Then, there exists at least one cycle in $G$. Remove one of the edges within a cycle. This leaves a connected graph on n vertices with n-2 edges which is impossible as a connected graph on n vertices must at least have n - 1 edges.

$\endgroup$
1
$\begingroup$

Yes, this seems like it is true, although you didn't prove a leaf must always exist, if you really want to be rigorous. And in the other part you didn't explain why if it contained a cycle you could remove an edge without the graph being disconnected, but I like the proof over all.

$\endgroup$
0
$\begingroup$

I have the following way of proving it. Let me know if you agree with it or not.

Suppose the graph on $n$ vertices with $n-1$ edges is not a tree. This implies it has at least $1$ polygon. Suppose in total there are $k$ edges involved in these polygons and we know that a polygon has as many edges as vertices, since polygons are of regular degree 2. Then, if we consider th egraph without the edges that form the polygons, then we have a connected graph with at least $n-k$ edges, since in a connected graph every vertex has degree at least 1. Thus, in total this would imply we have at least $n$ in all the graph. But this contradicts the fact that we have $n-1$ in the original graph. Thus it must be a tree.

$\endgroup$
0
$\begingroup$

The converse is not always true. Consider a disjoint graph with n vertices and n - 1 edges. Here we have n-1 edges but this is obviously not a tree. The assumption that G is connected is only for the forward implication.

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