Finding flaw in bogus k-coloring proof

Question

I'm following along an MIT discrete maths course, one of the assignments states the problem of finding the flaw in a proof for $k$-coloring (the course only considers simple graphs without loops):

False Claim. Let $G$ be a (simple) graph with maximum degree at most $k$. If $G$ also has a vertex of degree less than $k$, then $G$ is $k$-colorable.

a) Give a counterexample to the False Claim when $k = 2$.

Maybe I think a bit too simple about the problem, but it says "… If $G$ also has a vertex of degree less than $k$ …", that means that $G$ only needs to have at least one node with degree less than the maximum degree $k$.

So to answer a) I thought of this graph:

The maximum degree here is 2 and it also has one node that has degree less than 2, but you still need $k+1$ colors to color it, so the claim can't be true in this case.

Next, they also provide a bogus proof for the claim:

Identify the exact sentence where the proof goes wrong.

Induction hypothesis: P(n) is defined to be: Let $G$ be a graph with $n$ vertices and maximum degree at most $k$. If $G$ also has a vertex of degree less than $k$, then $G$ is $k$-colorable.

Base case: ($n=1$) $G$ has only one vertex and so is 1-colorable. So P (1) holds.

Inductive step: We may assume $P(n)$. To prove $P(n + 1)$, let $G_{n+1}$ be a graph with n + 1 vertices and maximum degree at most k. Also, suppose $G_{n+1}$ has a vertex, $v$, of degree less than k. We need only prove that $G_{n+1}$ is $k$-colorable.

To do this, first remove the vertex v to produce a graph, $G_n$, with n vertices. Removing v reduces the degree of all vertices adjacent to v by 1. So in $G_n$, each of these vertices has degree less than k. Also the maximum degree of $G_n$ remains at most k. So $G_n$ satisfies the conditions of the induction hypothesis $P(n)$. We conclude that $G_n$ is k-colorable.

Now a k-coloring of Gn gives a coloring of all the vertices of $G_{n+1}$, except for v. Since v has degree less than k, there will be fewer than k colors assigned to the nodes adjacent to v. So among the k possible colors, there will be a color not used to color these adjacent nodes, and this color can be assigned to v to form a k-coloring of $G_{n+1}$.

We need to identify where the proof goes wrong. This one I find a bit harder, as the proof is relatively long.

For me, the base case seems off. It reads:

Base case: (n=1) G has only one vertex and so is 1-colorable. So P (1) holds.

It's true that you can color a one node graph with one color. But the claim talks about a graph that has degree at most k (which is 0 in a one node graph) that also has a vertex with a degree less than k (which would be -1 or less?), but the single node in that graph has degree k (which is 0 and equals the maximum degree of that graph which is also 0).

Am I on the right track or is the proof going wrong somewhere else?

Answer 1

Your counterexample is not correct, as it has maximum degree $3$. Hint: think about disconnected graphs.

The problem with the proof is not the base case, that is fine (you are doing induction on $n$, not $k$, so $k$ is fixed and could be much more than the maximum degree for small cases). The issue is that when they remove a vertex $v$, they say each of its neighbours will now have degree less than $k$. What if it didn't have any neighbours?

Answer 2

Especially Lime's answer covers basically everything, also TMM comment makes a lot of sense. Because I wanted to draw a graph again, here is my updated answer to the problem:

So in this graph we have max. degree $k = 2$, and also one node with degree less than $k$ but still need $k + 1 = 3 $ colors.

Indeed the basecase is ok, because the one-node graph can be colored in $k$ colors, that's just fact and we are inducting on the number of vertices, so that's fine. I was interpreting the basecase too literal.

Now where the proof goes wrong, I think there are two ways to see it:

• like TMM said, if we say "Also, suppose $G_{n+1}$ has a vertex, $v$, of degree less than $k$. […] To do this, first remove the vertex $v$ to produce a graph, $G_n$ […]" but if the graph only had one such vertex and we remove it, then we can't make use of P(n). So that would mean the proof goes wrong at "So $G_n$ satisfies the conditions of the induction hypothesis P(n)"
• like Especially Lime said, if we think of a graph like shown above with disconnected nodes, "Removing $v$ reduces the degree of all vertices adjacent to $v$ by 1." doesn't work because if $v$ is disconnected there are no nodes adjacent to $v$ and therefore the degree of all other nodes in the graph is not affected by removing $v$.