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
    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.