What's the relation between the minimum independence number of graph G and the maximum independence number of G's complement? I think it should be the following, for some graph $G$:
$\alpha(G) \geq k \Rightarrow \alpha(\overline{G}) \leq \vert V(G) \vert - k + 1$
where $\alpha(G)$ is the independence number of $G$, $V(G)$ is the vertices of $G$, and $\overline{G}$ is the graph complement of $G$.
I wrote out a proof of this, but I'm not sure if it's right because somebody told me that the statement above is probably false.
Can someone explain why?
I'll post my proof as an answer, in case it will be useful to anyone.
 A: My proof of the relation in the question:
Suppose that $\alpha(G) \geq k$. This means that there exists a set $S \subseteq V(G)$ such that $S$ is an independent set of $G$ and $\vert S \vert \geq k$.
Let $S^\prime$ be an independent set of $\overline{G}$. $S^\prime$ can only contain at most one vertex that is in $S$ because $S$ is a clique of $\overline{G}$. Therefore $S^\prime \subseteq (V(G) \setminus S) \cup (S^\prime \cap S)$.
We have $-\vert S \vert \leq -k$, so the cardinality of $V(G) \setminus S$ satisfies: $\vert V(G) \setminus S \vert = \vert V(G) \vert - \vert S \vert \leq \vert V(G) \vert - k$. As stated above, the sets $S$ and $S^\prime$ share at most one vertex, so $\vert S^\prime \cap S \vert \leq 1$.
Based on the inequalities above, we have that $\vert S^\prime \vert = \vert V(G) \setminus S \vert + \vert S^\prime \cap S \vert \leq \vert V(G) \vert - k + 1$. Therefore we conclude that $\alpha(\overline{G}) \leq \vert V(G) \vert - k + 1$.
A: To put it more simply, eliminate $k$; you want to prove that
$$\alpha(G)+\alpha(\overline G)\le|V(G)|+1.$$
Proof: Let $S$ be an independent set in $G$ with $|S|=\alpha(G),$ and let $T$ be a clique in $G$ (i.e. an independent set in $\overline G$) with $|T|=\alpha(\overline G).$ Then $S\cup T\subseteq V(G)$ and $|S\cap T|\le1,$ so
$$\alpha(G)+\alpha(\overline G)=|S|+|
T|=|S\cup T|+|S\cap T|\le|V(G)|+1,$$
Q.E.D.
Of course, if $\alpha(G)\ge k,$ then $k+\alpha(\overline G)\le\alpha(G)+\alpha(\overline G)\le|V(G)|+1,$ i.e., $\alpha(\overline G)\le|V(G)|-k+1.$
