I'm trying to follow the MIT introductory mathematics for cs course.
In the reading on graph theory, the proof that a graph with maximum degree at most k is (k + 1) colorable is given as follows:
We use induction on the number of vertices in the graph, which we denote by n. Let P(n) be the proposition that an n-vertex graph with maximum degree at most k is (k + 1)-colorable.
Base case (n = 1):
- A 1-vertex graph has maximum degree 0 and is 1-colorable, so P (1) is true.
- Now assume that P (n) is true, and let G be an (n + 1)-vertex graph with maximum degree at most k.
- Remove a vertex v (and all edges incident to it), leaving an n-vertex subgraph, H. The maximum degree of H is at most k, and so H is (k + 1)-colorable by our assumption P (n).
- Now add back vertex v. We can assign v a color (from the set of k + 1 colors) that is different from all its adjacent vertices, since there are at most k vertices adjacent to v and so at least one of the k + 1 colors is still available.
- Therefore, G is (k + 1)-colorable. This completes the inductive step, and the theorem follows by induction.
Simple enough, but I'm confused as to why we need part 1 and 2 of the inductive step.
That is to say why do we need to create a (n + 1) vertex graph, remove an edge and then add it back again? Can't we just define H from the start to be a graph of size n with a maximum degree of at most k? Doesn't step 3 work just the same?