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?
Best Answer
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).