Complement of a Disconnected Graph is Connected Let $G$ be a disconnected graph. Prove that its complement $\bar{G}$ is connected.
I would like to check if my proof of the above (rather famous) problem is valid. It is as follows:
Since $G$ is disconnected, its vertex set can be partitioned into $2$ disjoint vertex sets, $V_1$ and $V_2,$  such that each vertex is only adjacent to vertices in the same set as it. Hence, in $\bar{G}$, each vertex is adjacent to all the vertices in the other set, and will not be adjacent to any vertex in the same set as it. in other words, $\bar{G}$ is a complete bipartite graph, which is clearly connected, so we are done.
 A: This is not correct.  It is in general not true that each vertex in $V_1$ will be adjacent to all other vertices in $V_1$. That would only be the case with graphs that are a union of several complete graphs.
So the complementary graph is certainly not always a complete bipartite graph, it could have more edges as well.  But the important thing here is that this complete bipartite graphs is always a subgraph of $\bar{G}$ containing all vertices of $\bar{G}$. Therefore it is indeed connected.
A: This answer may be too late, but you can't assume there are only 2 disjoint vertex sets, and you also can't assume that the vertices in some $V_i$ are adjacent to one another. You're on the right track, however, because we do want to partition V into disjoint sets. I've included a formal proof that uses this approach.
Edit: As @JaapScherphuis pointed out, I was wrong in assuming we need to define more than two sets since we need only prove the graph is connected. So another (less complicated) approach to the proof is to instead consider the vertex set $V_1$ of some component in $G$ and the set $V \setminus V_1$ to complete the proof.
Proof:
Let $G = (V,E)$ be a disconnected graph and let $\overline{G}$ be the complement of $G$. Define $\sim$ as an equivalence relation such that for any $x,y \in V(G), x \sim y$ iff there exists a walk between x and y in $G$. Since $G$ is disconnected, then $\coprod_{i = 1}^{n} V_i$ is a partition of $V$ into classes of the relation $\sim$ and $n > 1$. Let $z_i, z_j \in V$, and let $\{ z_i, z_j \} \in \binom{V}{2} \setminus E$ (i.e. let $z_i, z_j$ be arbitrary vertices such that they do not share an edge in $G$). Since $\binom{V}{2} \setminus E$ is the edge set of $\overline{G}$, $z_i \sim z_j$ in $\overline{G}$. If $\coprod_{i = 1}^{n} V_i = \emptyset$, $\overline{G}$ is connected since $\{ z_i, z_j \} \in \binom{V}{2} \setminus E$. Otherwise, we consider $v_i, u_i \in V_i$, which means $ \{ v_i, u_i \} \notin \binom{V}{2} \setminus E$ (i.e. $v_i$ and $u_i$ are in the same component and share an edge in $G$ but do not share an edge in $\overline{G}$). Additionally, let $v_j \in V_j$ where $j \neq i$(i.e. in a different component). Then, a walk between $v_i$ and $u_i$ is formed with the edges $\{ u_i, v_j \}$ and $\{ u_i, v_i \}$ (since $\sim$ is an equivalence relation and therefore transitive). Thus, a path exists between all $v_i, v_j \in V$.
