# Proving that A connected graph on $n$ vertices is a tree iff it has $n-1$ edges

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?

• 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.
– user208649
Mar 19, 2015 at 19:18

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