# Prove that a graph with $n$ vertices and $k$ edges will have at least $n-k$ connected components by induction on $k$.

My question is more regarding the induction process and I want to make sure I'm not making a build-up error in the proof.

Proof by induction on $$k$$, the number of edges. Let $$G$$ be a graph with $$n$$ vertices.

Base case: for $$k = 0$$ the claim holds as we have $$n$$ isolated vertices and thus, $$n - 0$$ connected components.

Inductive Hypothesis: suppose the claim holds for all $$j\geq0$$. That is every graph with $$n$$ vertices and $$j$$ edges has at least $$n - j$$ connected components.

*Inductive Step: Suppose we now have $$j + 1$$ edges. We know that for $$j$$ edges the claim holds from the inductive hypothesis. If we add an edge to the graph from the inductive hypothesis then we have the following cases:

1)We connect two components thus decreasing the number of connected components by $$1$$. Then the number of connected components is $$n - j - 1 = n - (j +1)$$.

2)We add an edge within a connected component, hence creating a cycle and leaving the number of connected components as $$n - j \geq n - j - 1 = n - (j+1)$$.*

In either case the claim holds, therefore by the principle of induction the claim is true for all graphs.

• If I were grading this, I'd be happy to award full marks – bounceback Jan 11 at 3:52

I don't know what a "build-up" error is, but there is a minor, technical issue with your proof:

When proving the induction step, you should be starting from an arbitrary graph with $$n$$ vertices and $$j + 1$$ edges, and conclude from there. You do start with such a graph, but then fail to use it. Instead, you say

If we add an edge to the graph from the inductive hypothesis then we have...

To which graph are you adding an edge here, and what does it have to do with the graph with $$j + 1$$ edges? What you are doing is "building up" (is this a "build-up" error?) all the graphs you can from the inductive step, but failing to account for the possible graphs that cannot be built in this way!

Of course, every graph of $$j + 1$$ edges can be built up from a graph with $$j$$ edges: simply remove one edge. This is how you should be arguing. Start with a graph $$G$$ of $$j + 1$$ vertices, fix one edge $$e$$, and consider the graph $$G'$$ with $$e$$ removed. Then $$G'$$ has at least $$n - j$$ connected components. Adding $$e$$ back in to form $$G$$, by the arguments supplied, will remove at most one connected component, giving you at least $$n - j - 1$$ connected components.

(P.S. I don't want to contradict bounceback's comment; I too would award full marks, because your proof is almost 100% correct and would be doing better than 98% of my other students' efforts!)

• so I should use a graph G with j+1 edges in the inductive hypothesis and then remove an edge in the inductive step? My idea was to take the graph from the inductive hypothesis and add an edge to get j + 1 edges. – Matteo Ciccozzi Jan 11 at 4:08
• Yes, you should do that. While it is incredibly intuitively obvious that any graph of $j + 1$ edges may be obtained from a graph of $j$ edges by adding in the right edge, this is still a leap in logic that your proof doesn't explain (or even address). Your goal was to show that every graph $G$ with $j + 1$ edges has at most $n - j - 1$ connected components; but you don't relate this other graph $G'$ with $j$ edges to $G$ at all. Certainly not just any arbitrary choice of $G'$ will work! For most $G'$, adding a single edge will not get you $G$ back! – Theo Bendit Jan 11 at 4:14
• @Matteo Consider a false proof: every natural number $n$ is a power of $2$. We can fake-prove it using induction on $p(n) = \lfloor \log_2 n \rfloor$. If $p(n) = 0$, then $n = 1$, which is $2^0$; our base case is done. Suppose it's true that, if $p(n) = k$, then $n$ is a power of $2$. Then, taking any number $n$ from with $p(n) = k$, we can form a number $2n$ with $p(2n) = k + 1$. Thus, the claim holds for $p(2n) = k + 1$, and so every number is a power of $2$! – Theo Bendit Jan 11 at 4:19
• @Matteo The above "proof", of course, is false. The induction step doesn't work, because it only builds from the inductive hypothesis. It doesn't work for any $n$ such that $p(n) = k + 1$, because we never started with an arbitrary such $n$. We began from the (one) $n$ covered by the inductive hypothesis, and thereby constructed $2n$, missing almost all $n$ such that $p(n) = k + 1$. That's why you need to start with an arbitrary case from your inductive step, and relate it back to your induction hypothesis. – Theo Bendit Jan 11 at 4:22
• @Matteo Sorry to hammer this home, but take from the fake proof, a concrete example of $n = 3$. Then $p(n) = 1$. All our "proof" gives us is that, if we take a number $m$ with $p(m) = 0$, then $p(2m) = 1$. Is $2m$ the same as $3$? The proof doesn't say. Just like with your proof, the graph with $j$ vertices that you start with, then add an edge to, may not be the arbitrary graph $G$ with $j + 1$ edges that you're aiming for. Maybe such a graph cannot be achieved in this way. (Well, it obviously can when you think about it, but you should include that in your proof.) – Theo Bendit Jan 11 at 4:29