3
$\begingroup$

I'm having some trouble proving the following theorem:

Theorem: A connected graph on $n$ vertices is a tree iff it has $n-1$ edges

I sort of proved it one way, and I'm stuck the other way around.

Necessity ($\Rightarrow$):

A tree with $n$ vertices has $n-1$ edges.

Basis step ($n=1$):

A tree with one vertex has no edges

Assume a tree with $k\leq n$ vertices has $n-1$ edges

For $k+1$,

Let the added vertex be $u$, if $deg(u)=0$ then we don't have a tree, so $deg(u)>0$. If $deg(u)>1$ then we have a cycle (how do I argue about this?) so again we don't have a tree , so $deg(u)=1$.

Total number of edges = $(n-1) +1 = n \therefore$

$\therefore P(1) \land \forall k, P(k)\Rightarrow P(k+1)$

Sufficiency ($\Leftarrow$)

A connected graph with $n-1$ edges is a tree

How can I prove this part? Also, is my induction ok?

$\endgroup$
1
  • 1
    $\begingroup$ The induction misses several cases. The most effective way is to delete a pendant vertex from the $n$ vertex graph, apply the inductive hypothesis, and then reattach the deleted vertex. $\endgroup$
    – user208649
    Mar 19, 2015 at 19:18

1 Answer 1

4
$\begingroup$

Hint: Argue that a connected graph with $n$ vertices and $n - 1$ edges cannot have a cycle and is thus a tree.


And yes, your induction looks fine, although you seem to be restricting yourself to a leaf. Maybe you can try a more general case by detaching the new vertex and considering the two disconnected components (both of which will satisfy the inductive hypothesis).

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