1
$\begingroup$

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?

  • 0
    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](http://onlinelibrary.wiley.com/doi/10.1002/9780470400531.eorms0146/pdf).2012-10-11
  • 0
    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.2012-10-11
  • 0
    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.2012-10-11
  • 0
    Well then why on earth didn't you say that? You could have saved me a lot of work.2012-10-11
  • 0
    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!2012-10-11
  • 0
    I undeleted my answer with a counterexample for both statements. Regarding your question about equivalence, what sort of equivalence do you mean? As Gerry pointed out, the second statement should have a universal quantifier over $G$. If you add that, there are no free variables in either formula, so asking whether they're equivalent is really just asking whether they have the same truth value. By my counterexample they do, so they're equivalent. But you seem to mean something else, something like formally equivalent regardless of the meaning of the symbols. That they are not.2012-10-11

2 Answers 2

1

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.

  • 0
    In fact both statements are false (see my answer).2012-10-11
1

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.