2
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ The problem is that the IH requires there to be at least one vertex of degree less than k. If we have exactly one such vertex in Gn+1 and remove it, we cannot invoke the IH to claim that Gn is k-colorable, because Gn may only contain vertices of degree exactly k. $\endgroup$ – TMM Aug 17 '17 at 9:05
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yeah, you are correct. My counter example is totally off of course. Yeah, disconnected graphs are the way. $\endgroup$ – Max Aug 17 '17 at 9:07
0
$\begingroup$

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:

enter image description here

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.