Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question

Prove, by induction on k, that a connected component of k nodes has at least k − 1 edges.

-

Outline of Proof: Let $G$ be a connected graph with $k$ vertices. If every vertex of $G$ has at least two edges, then the number of edges must be at least $k$.

If not every vertex of $G$ has two or more edges, let $v$ be a vertex that has only one edge. Remove $v$, and $v$'s single edge. The remaining graph $G'$ is connected, has $k-1$ vertices, and therefore by the induction hypothesis has at least $k-2$ edges. Put our vertex $v$ back, and its edge. That gets us to at least $k-1$ edges.

-
I completely understand what you are saying, but I am unsure about how I would go about expressing that with a math expression. – MZimmerman6 Dec 2 '12 at 2:52
I have a similar tree problem which I wish to use the node removal method to prove. I also want to know how a complete proof by induction looks like. Thanks. – xiamx Dec 2 '12 at 3:38
Usual induction proof. Result is true for $0$ vertices (or $1$ if you prefer). We show if it is rue for any connected graph with $k-1$ vertices, it is true for any connected graph with $k$ vertices. (If you prefer going $k$ to $k+1$, need minor changes in my answer.) There are two cases: (i) Every vertex has $\ge 2$ edges. Then we don't even care about connectedness, the usual every edge has $2$ vertices gives us a count of $\ge k$. (ii) there is a vertex with $1$ edge. Do argument as I did. You will have to prove that the graph obtained by deleting the vertex, edge is still connected. – André Nicolas Dec 2 '12 at 3:39