Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $G$ be an undirected, simple graph, and let $\alpha(G)$ denote the independence number of $G$, i.e., the size of a maximum independent set (stable set) in $G$. A graph is $\alpha$-critical if for every edge $e$ of $G$, we have $\alpha(G - e) > \alpha(G)$.

Conjecture: for every $\alpha$-critical graph $G$ without isolated vertices, for every maximum independent set $S$ in $G$, there is a maximum independent set $S'$ in $G$ that is disjoint from $S$.

The conjecture is true for the simplest classes of $\alpha$-critical graphs, the graphs $K_n$ ($n \geq 2$) and the odd cycles. It also seems to be true for the list of minor-minimal obstructions to having a vertex cover of size at most five, which are also $\alpha$-critical. Is it true in general?

Thanks in advance!

share|cite|improve this question
Bart, I have ``Matching Theory''. To send it to you? – Boris Novikov Feb 12 '13 at 11:20
Thanks, Boris. The theorems in the book do not seem to answer my question, unfortunately. – Bart Jansen Feb 13 '13 at 9:26

3 Answers 3

Well, take a graph on $n\ge 3$ vertices with exactly one edge. Clearly, it's $(n-1)$-critical, but does not satisfy your conjecture.

share|cite|improve this answer
You're right, of course. I should have added the condition that $G$ contains no isolated vertices, which I just did. (I'm used to thinking about the graphs as minor-minimal obstructions to having a vertex cover of a certain size; $\alpha$-critical graphs are only obstructions if they do not have any isolated vertices.) – Bart Jansen Feb 13 '13 at 9:28

I don't think so. You really mean maxiMUM, not maxiMAL, right?

If so, take a complete bipartite graph $K_{m,n}$ with $m$ less than $n$, so the maximum critical set is the big part in the bipartition and is of size n. This graph isn't $\alpha$-critical, clearly, but its maximum independent set is so big that there's a pigeonhole problem with finding a disjoint second one.

It seems to me that if you delete edges from G you can only increase the independence number, so (*) do this iteratively without disconnecting G until the result is $\alpha$-critical.

This should give you a counterexample unless this last step (*) is flawed somehow, which might well be the case, I confess - I haven't thought it through. But rather than agonizing about whether it's possible, you can implement this randomly with a computer program, for explicit small m,n, until you have either generated an explicit counterexample, or waited for such a long time as to convince yourself that it's worth trying to find the error. I might do it if I have a chance today.

EDIT -- I was wrong - step (*) is in fact flawed, because it disconnects the graph before it becomes $\alpha$-critical. Interesting!

share|cite|improve this answer
I'm pretty sure (*) fails emphatically. As evidence, consider the case in which the edges form a perfect matching. Here $n$ is the maximum stable set still, but since $n>m$ the graph is disconnected. Moreover it fails for $(m,n)=(1,2)$, and I think you should be able to prove that it fails in general using strong induction and observing the new maximum stable set when you remove an edge. – Andrew D. King Mar 13 '13 at 17:44
I do indeed mean maxiMUM rather than maxiMAL. It is known that the alpha-critical bipartite graphs are exactly the perfect matchings, so these cannot give a counterexample: all perfect matchings have two disjoint maximum independent sets. – Bart Jansen Mar 14 '13 at 9:09

Late answer, but for future reference (so that anyone reading this thread won't spend as much time as I did trying to prove the conjecture) the conjecture is false, with the following simple graph as a counterexample. Let $G$ be the following graph

Counterexample of strong conjecture.

One can see that $\alpha(G) = 4$. It is also easy to see that if we remove any of its edges we obtain a graph with independence number 5, whence it is $\alpha$-critical. The vertex set $S = \{1,4,7,9\}$ (or, alternatively, $S=\{2,5,8,9\}$) is a maximum independent set with the property that $H = G \setminus S$ (the graph formed by removing the vertices in $S$, and all edges incident to them, from $G$) is just the graph consisting of three $K_2$-components. Thus $\alpha(H) = 3$ and therefore the maximum size of any independent set in $G$ disjoint from $S$ is three.

Another reason for reopening this thread is that I would be interested to know if the following weakening of the conjecture could be true:

Weak conj. for every $\alpha$-critical graph $G$ without isolated vertices, there exists a maximum independent set $S$ in $G$ and a maximum independent set $S′$ in $G$ that is disjoint from $S$.

I somehow get the feeling that this is unlikely to be true, however I am unable to find a counterexample. The graph above, that provides a counterexample to the stronger conjecture, does indeed satisfy this weaker version, for example by taking the maximum independent sets $S = \{1,2,4,9\}$ and $S' = \{5,6,7,8\}$. There is one more (connected) graph with a counterexample to the stronger conjecture that I know of;

Second counterexample. with $S = \{1,4,7,9\}$.

However, also this graph satisfies the weaker version of the conjecture (take e.g. $S = \{1,3,4,9\}$ and $S' = \{0,6,7,8\}$).

I know of no more counterexamples to the stronger conjecture and I believe that the only graphs that provide counterexamples with less than $11$ vertices are the two graphs mentioned above. Thus I believe that any counterexample to the weaker conjecture would have to have at least $11$ vertices.

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.