Disjoint Maximum Independent Sets in $\alpha$-critical graphs 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!
 A: 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

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;
 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.
A: 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.
A: 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!
