# Question about the proof that 'A graph with maximum degree at most k is (k + 1) colorable

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):

1. A 1-vertex graph has maximum degree 0 and is 1-colorable, so P (1) is true.

Inductive step:

1. Now assume that P (n) is true, and let G be an (n + 1)-vertex graph with maximum degree at most k.
2. 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).
3. 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.
4. 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?

• You could define $H$ as you wish, but then you would have to prove that $G$ can be constructed from $H$ by adding a vertex and some edges. You could say that $H$ is a graph that we can use to construct $G$ by adding a vertex, but then you have to prove that such graph $H$ exists. Starting from $G$ and then removing and re-adding that vertex is the simplest way which takes care of all such issues. – dtldarek Sep 30 '14 at 11:22

## 1 Answer

I think you're asking "Why can't we prove the $n+1$ node case by starting with an $n$-node graph and adding a vertex?" The answer is "Because that proves the $n+1$ node case only for graphs that can be constructed that way, which might, a priori, not be all of them." What steps 1 and 2 do is show how, given an $n+1$-node graph $G$, to find an $n$-node graph $H$ which, when a new node and the right edges are added, becomes the graph $G$ that you're interested in.

That seems completely trivial, and maybe in this case it actually is. But in general, for inductions that prove things on larger and larger sets, it's not always clear how to get from an element of the smaller set to every possible element of the larger set. Students often think that they see "an obvious way" that's in fact wrong.

As an example: consider and $n \times n$ symmetric matrices $M$ whose "outer" values (i.e., those for which one index is either 1 or $n$) are all "1"s, and whose inner values are integers other than one.

It's pretty clear that to get from a size-$n$ example of this to a size $n+1$ example, you can't just add a row at the bottom and a column at the right, but you might think, "yeah, but you could just add a row in the MIDDLE and a column at the corresponding position in the middle", with the condition that the inserted row start and end with 1 and have non-1s in the other places.

Clear? Pretty much. Unfortunately, it's also wrong. You can't get from the (only) $1 \times 1$ example of this kind of matrix, namely $$ to the only $2 \times 2$ example (which is all $1$s) through this "obvious" step.

• Great example with matrices! – mattecapu Sep 30 '14 at 13:22
• Thank you, I think I've got it now. Would I be correct in saying that if you start by defining H as any n-node graph and then add a node to it, you are only proving P(n+1) for a specific case (the type of graph that can be created from graph H by adding a node). Whereas if you start by defining G as any n+1 graph and then remove and add a node, you are proving P(n+1) for any n+1 graph? – mallardz Sep 30 '14 at 15:49
• That's exactly right. And in this particular case, those two sets happen to coincide, and that's so obvious to some students that they never imagine that there could be a situation in which that DOESn't happen...which is why I built that matrix example. – John Hughes Sep 30 '14 at 20:38