Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Any suggestions? Thanks in advance

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.