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.
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
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)$
A connected graph with $n-1$ edges is a tree
How can I prove this part? Also, is my induction ok?