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


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.

  • 1
    $\begingroup$ I completely understand what you are saying, but I am unsure about how I would go about expressing that with a math expression. $\endgroup$ Dec 2 '12 at 2:52
  • $\begingroup$ 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. $\endgroup$
    – xiamx
    Dec 2 '12 at 3:38
  • $\begingroup$ 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. $\endgroup$ Dec 2 '12 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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