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.
Best Answer
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
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!)