Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been given two statements and told that they are equivalent, but I'm having a hard time convincing myself of that. The two statements are:

(1) "Every graph G has a minimum colouring in which some colour-class has $\alpha(G)$ vertices" and (2) "In every minimum colouring of a graph, one of the colour-classes is a largest independent set", where $\alpha(G)$ is the size of the largest independent set of G.

Formally, I believe these would be: $$\forall G \space \exists\mathcal{C} \mid \exists C\in\mathcal{C} \mid |C|=\alpha(G)$$ and $$\forall \mathcal{C} \space \exists C\in\mathcal{C} \mid |C|=\alpha(G)$$ where G is a graph, $\mathcal{C}$ is a minimum colouring of G, C is a colour-class of $\mathcal{C}$ and $\alpha(G)$ is the size of a largest independent set.

While this is for an assignment, the assignment problem is not to determine if these two statements are equivalent, but to prove or disprove them (assuming they are the same) (tagging with homework just in case). I believe I have already done that, but my solution of using a counterexample seems to disprove statement (2), not both statements. Which leads to my question:

Could somebody please help me figure out if the original two statements are equivalent or not?

share|cite|improve this question
As Gerry has pointed out, (2) is false; for instance think of a central vertex that's part of a triangle and also has lots of leaves attached to it; then you can colour any number of the leaves in the two other colours used for the triangle, and neither colour class has to be maximal. Since (2) is false, I'd give some thought to counterexamples for (1) before spending too much effort trying to prove it. Note that (1) is easy to prove if you replace "largest independent set" by "maximal independent set"; see this paper. – joriki Oct 11 '12 at 7:16
Sorry, I posted a counterexample and only then noticed that one option in your assignment was to disprove these statements. I've deleted the answer; let me know if you'd like to see it. – joriki Oct 11 '12 at 7:49
I had found a counterexample already (actually, it was using a graph that contained a triangle and leaves). However, the counterexample seems to disprove (2), but not (1). I then started to question whether the two given statements were actually equivalent, and hence the question. – Travis Oct 11 '12 at 13:04
Well then why on earth didn't you say that? You could have saved me a lot of work. – joriki Oct 11 '12 at 13:05
Sorry, after re-reading it this morning, I realize the wording of the OP may not be the clearest. I thought the title and the only actual question in the post would be enough. Will edit. Also, saved the paper for later reading, I do appreciate that! – Travis Oct 11 '12 at 13:13
up vote 1 down vote accepted

First, I think your second formal statement should begin with $\forall G$, since (2) is really "For every graph, in every minimum coloring of the graph, etc."

Second, since the first formal statement has $\exists\cal C$ where the second has $\forall\cal C$, I don't see how to prove they're equivalent.

And third, at the risk of telling you more than you want to know, I think (2) is false.

share|cite|improve this answer
In fact both statements are false (see my answer). – joriki Oct 11 '12 at 7:46

Both statements are false (and therefore in a certain sense equivalent). A counterexample is given by the graph

         a     c
         |     |
         b     d 
        / \   / \
       a   a-b   c
        \ /   \ /
         b     d
         |     |
         a     c

with chromatic number $2$ which admits only one $2$-colouring, with vertices of types $a$ and $d$ forming one colour class and those of types $b$ and $c$ forming the other, with both classes having $6$ elements, whereas the maximum independent set consisting of the vertices of types $a$ and $c$ has $7$ elements.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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