Take the 2-minute tour ×
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|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

2 Answers 2

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

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.