Background: This is a bit of a tedious proof, and while intuitively one can understand how to go about it, we will need to formalize a few other statements and prove them before we can do this proof.

I shall provide definitions of the term Bipartite (= 2-Partite), and also prove the theorems we will need to prove this statement.

1) Bi-Partite (2-Partite) - A graph $G=(V,E)$ is 2-partite iff $\exists U,W\subset V\left(G\right)\ni ,U\cap W=\varphi$ and $U\cup W=V\left(G\right)$ and, furthermore, $E\left(G\right)=\{uv:u\in Uandv\in W\}$

Informally, this is a partitioning of a graph into two non-intersecting subset of vertices, such that, no 2 vertices in the same subset are adjacent.

a) In the event that we have a disconnected graph, i.e., $G=(V,E),\ni ,k\left(G\right)>1$ , it can only be 2-partite if all of its connected components are 2-partite.

Proof - This is fairly easy to see. We see that if $\exists CC\left(G\right),\ni ,CC\left(G\right)\ne 2-partite$, then, G itself can never be 2-partite, because, $G=C{C}_1\cup C{C}_2\cup ...\cup C{C}_n$ , and so, as $\nexists uv\in E\left(G\right)$ , for some $u$ in the non-bipartite component, and $v$ in some bipartite component, we cannot split those vertices into any 2 existing subsets designed for the other Connected Components, as by doing so, we will be forced to put at least 2 vertices connected by an edge in one of those subsets.

b) Given $G=(V,E)$ , then, G = 2-partite, iff, $\nexists C_{odd}\subset G$.

Proof - Basically, this statement says that in order for any graph to be Bi-partite, none of its possible subgraphs can be an odd cycle. And, of course, vice-versa. We will show 2 cases:

1) Given there is an odd cycle subgraph in a graph, it is not 2-partite.

2) Given a graph is 2-partite, there is no odd-cycle in it.

1) We know that $\exists C_{odd}\subset V\left(G\right)$. Therefore, in order to the Graph G, we will also need to make sure that we can partition this cycle. In order to partition the vertices, we will manually assign vertices that are adjacent to each other to each other opposing partition sets. That is, suppose, $\exists U,W\subset V,\ni ,$ vertices $v\in C_{odd}$ are put into U and W alternatingly if they are adjacent. So, let $C_{odd}=(V_{odd},E^{{}^{\text{'}}})$ where $V_{odd}=(v_1,v_2,...,v_{2k+1})$ for some $k\in \mathbb{Z}$ Now, let us start by assigning $v_1\in U$ and $v_2\in W$ and so on. We see then, that, $v_{odd}\in U$, and $v_{even}\in W$. Therefore, $v_{2k+1}\in U$, and so is $v_1\in U$. However, as we have a Cycle, we know that, $v_{2k+1}{v}_1\in E\left(G\right)$. Therefore, we have that 2 adjacent vertices belong to the same subset on partition, and there is no other way of partitioning. This implies that if we have an odd cycle, there exists no way to partition the Graph in a Bipartite manner.

2) Given a 2-partite graph. if there exists an odd cycle in it, we know that $v_{2k+1}$ and $v_1$ are not in the same set. Then, we have that, as there is, at minimum, 1 cross edge between two vertices in U, W (not counting the edges due to the cycle), then, we have that: $\sum$ $deg\left(v\right)$ = $2(2k+1)$ = $4k+3$ = $(4k+2)+1$, which means that the sum of degrees is odd, and this violates the fundamental theorem of Graph Theory, that the sum of all edges is equivalent to an even number. The very fact that this possibility exists implies that we cannot have a 2-partite graph with an odd cycle.

Now, we shall use the 2 facts above to show our main claim:

The only case we really need to show that given a Graph $G=(V,E),\ni ,k\left(G\right)=1$ and $G=2-partite$ , $\overline{G}\ne 2-partite$. Now, we have that, as G is 2-partite by definition, $\nexists C_{odd}\in V\left(G\right)$ . Therefore, all we need to show that in $\overline{G}$ , $\exists C_{odd}\in$ $V\left(\overline{G}\right)$. This would imply that $\overline{G}$ is not 2-partite.

So, we now have to show the existence of $C_{odd}$ for graphs G that have even cycles or are acyclic. Let us prove these cases: 1) $G=(V,E)\ni ,\exists C_{even}\in V\left(G\right)$ . We will then show that $\exists K_{odd}\subset \overline{C_{even}}$ , where, $\overline{C_{even}}\in \overline{G}$ . Now, we know that there must be at-least 6 vertices (for the case of 4 vertices in the cycle, there must exist at-least 1vertex not in the cycle, and connected to some vertex in the cycle, leading to a 3-cycle in the negated graph), and let us donate the number of edges in $C_{even}$ as $e$. In $C_{even}$ , we see that $\left|E\right(\overline{C_{even}}\left)\right|$ = $e(e-1)/2-\left(e\right)$ = $e^2/2-3e/2$. We notice that this number is even and greater than $(e-1)$ itself. Therefore, we see that, as there must exist for some vertex $v\in V\left(G\right)$ , at least 2 vertices $u,w\in V\left(G\right),\ni ,(vu,vw,uw)\notin E\left(G\right)$. We have that, in $\overline{G}$ , $(vw,uw,uw)\in E\left(\overline{G}\right)$, implying that there exists a 3 cycle. Now, in order for 3 such vertices to exist, they need to be, at minimum, at alternating distances from each other, that is, $d_{min}(v,w)=2$ , $\forall v\in C_{odd}\subset \overline{C_{even}}$. As the smallest odd cycle is a 3-cycle, we need a 6-cycle complement to always create a 3-cycle as one of its subgraphs, showing the inability to have it exhibit the property of being 2-partite. Therefore, as $(vw,uw,uw)\in E\left(\overline{G}\right)$, we have that, $C_{odd}=(\{u,v,w\},\{uv,vw,uw\})\subset \overline{G}$ , and therefore, $\overline{G}\ne$ 2-partite. 2) In the event that we have $G=(V,E)\ni ,G$ = Acyclic Graph. Now, as $\left|E\right(G\left)\right|\le (n-1)$, where, $n=\left|V\right(G\left)\right|$ ,$\exists (v_1,v_2)\in V\left(G\right),\ni ,deg\left(v_1\right)$ = $deg\left(v_2\right)$ = 1. As $\sum$ $deg\left(v\right)=2(n-1)$ , $\forall v\in V\left(G\right)$ , we see that, provided $k\left(G\right)=1$, $\exists (v_1,v_2),\ni ,deg\left(v_1\right)=deg\left(v_2\right)=1$ . Now, as this is the case, given a graph of atleast 5 vertices, there exists at least 1 vertex $w,\ni ,(v_{1}w,v_{2}w)\notin E\left(G\right)$. Then, we have that, as, $deg\left(v_1\right)=deg\left(v_2\right)=1$ and $\left|V\right(G\left)\right|\ge 5$ , $v_1{v}_2\notin E\left(G\right)$. Finally, we see that $(v_1{v}_2,v_{1}w,v_{2}w)\in E\left(\overline{G}\right)$ , implying that $\exists \left(3_{-}cycle\right)\subset \overline{G}$. Therefore, we see that $\overline{G}\ne$ 2-partite. Therefore, our original claim is proved.

QED.