1
$\begingroup$

Prove the following Theorem. If $G$ is a connected graph with $n$ vertices and $n - 1$ edges, then $G$ is a tree.

I am still new to proof methods and not sure if this is the correct use of induction.

Base case: $n = 1$. Here, $G$ has $0$ edges and is a tree.

Assume every connected graph with $k$ vertices and $k-1$ edges is a tree.
Let $G$ be a connected graph with $k+1$ vertices that contains at least one cycle (no amount of edges are specified).

Let $m$ be the number of edges removed. Remove edges from each cycle to form a new graph $G'$.

$G'$ is a tree with $k-1$ edges and $k+1$ vertices. $G$ has $k-1+m$ edges.

If $m=0$ then $G' = G$ and $G$ is a tree.

$\endgroup$
  • 1
    $\begingroup$ How do you know it's still connected after removing one edge from each cycle? $\endgroup$ – TokenToucan May 20 '15 at 17:30
2
$\begingroup$

Your base case holds.

Suppose we have a cycle-free, connected graph $G$ with $n$ vertices. and $n-1$ edges.

Because $G$ is cycle-free, there is a vertex with degree $1$. Delete this vertex.

We are left with a connected graph $G'$ with $n-1$ vertices and $n-2$ edges, which is a tree by induction. Reattaching the former pendant vertex does not introduce a cycle into the graph, as it had degree one, so the graph $G$ must be a tree.

**

This is the standard proof - I don't think it is possible to make your proof work. You do establish the inductive hypothesis, and work on a graph with $k+1$ vertices, which is good. However, your proof doesn't appeal to the inductive hypothesis later.

Additionally, it's not clear how you arrive at "G' is a tree with k-1 edges and k+1 vertices" (which is not a true statement). I think you're trying to translate the proof that trees are acyclic into a proof by induction.

$\endgroup$
  • $\begingroup$ Why didn't you use a "n+1" when doing the induction proof? Isn't the "next step" always required for an induction proof? $\endgroup$ – onesevenfour May 20 '15 at 17:54
  • 1
    $\begingroup$ I used $n$, and assumed that it was true for all numbers up to $(n-1)$. This is equivalent to using $(n+1)$ and assuming that it is true up to $n$. $\endgroup$ – TokenToucan May 20 '15 at 17:55

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.