I was going through the text "Introduction to Graph Theory" by Douglas West where I came across the following theorem.
Theorem. The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n \leq 2^ k$ .
Proof: We use induction on $k$.
Basis step: $k = 1$. Since $K_3$ has an odd cycle and $K_2$ does not, $K_n$ is itself a bipartite graph if and only if $n \leq 2$.
Induction step: $k > 1$. We prove each implication using the induction hypothesis. Suppose first that $K_n = G_1 \cup . . . \cup G_k$ , where each $G_i$ is bipartite. We partition the vertex set into two sets $X$, $Y$ such that $G_k$ has no edge within $X$ or within $Y$. The union of the other $k - 1$ bipartite subgraphs must cover the complete subgraphs induced by $X$ and by $Y$. Applying the induction hypothesis to each yields $|X| \leq 2^{k-1}$ and $|X| \leq 2^{k-1}$, so $n \leq 2^{k-l} + 2^{k-l} = 2^ k$ .
Conversely, suppose that $n \leq 2^ k$ . We partition the vertex set into subsets $X$, $Y$, each of size at most $2^{k-l}$. By the induction hypothesis, we can cover the complete subgraph induced by either subset with $k - 1$ bipartite subgraphs. The union of the $i$th such subgraph on $X$ with the $i$th such subgraph on $Y$ is a bipartite graph. Hence we obtain $k - 1$ bipartite graphs whose union consists of the complete subgraphs induced by $X$ and $Y$. The remaining edges are those of the biclique with bipartition $X$, $Y$. Letting this be the $k$th bipartite subgraph completes the construction.
It's proof seem to be a bit difficult for me to understand in the first go, as here the author is talking about certain steps/constructions, which could have been better grasped if the material would have been provided with supporting figures. So this is my attempt of understanding the proof intuitively using figures.
First let us work out a simple example as follows:
On the left we have $K_4$. Now since $n=4=2^2$ we find it can be expressed as a union of two bipartite graphs as shown in the right (in red and cyan).
Now let us analyze each step of the proof.
We use induction on $k$.
Here $k$ is the induction parameter
Basis step: $k = 1$. Since $K_3$ has an odd cycle and $K_2$ does not, $K_n$ is itself a bipartite graph if and only if $n \leq 2$.
When $k=1$ it means that the complete graph $K_n$ can be expressed a union of only $1$ bipartite graph. Now this is possible only when the $K_n$ is itself a bipartite graph.
Now let us check for $n=4,3,2,1,..$
For $n\geq 3$ each of the $K_n$ shall have $C_3$ present in it, which being an odd cycle the graph as a whole shall not be bipartite.
For $n\leq 2$ this problem of having an odd cycle does not arise and as such the graph as a whole is a bipartite graph.
So we have proof for basis step as written in the text.
Induction step: $k > 1$. We prove each implication using the induction hypothesis. Suppose first that $K_n = G_1 \cup . . . \cup G_k$ , where each $G_i$ is bipartite.
Our main aim should be such that for the current $k$ we can make use of the hypothesis assumed true for $k-1$.
We partition the vertex set into two sets $X$, $Y$ such that $G_k$ has no edge within $X$ or within $Y$. The union of the other $k - 1$ bipartite subgraphs must cover the complete subgraphs induced by $X$ and by $Y$. Applying the induction hypothesis to each yields $|X| \leq 2^{k-1}$ and $|X| \leq 2^{k-1}$, so $n \leq 2^{k-l} + 2^{k-l} = 2^ k$ .
We assume that our system is already having $k-1$ bipartite graphs ($G_1,G_2,...G_{k-1}$) and now we are working with the $k$th bipartite graph ( which is also present in the system). Now suppose that the $k$th bipartite graph is considered, only as far as its partite set is concerned. We are not considering its edges currently.
Let $X$ and $Y$ be its two partite sets.
Now we are only left to add the edges from $X$ to $Y$ to make the entire graph a complete graph. Without the edges from $X$ to $Y$, each of $X$ and $Y$ are actually $K_{|X|}$ and $K_{|Y|}$.
Now without the $i$ th bipartite graph, we have $k-1$ bipartite graphs in this system, now using the induction hypothesis, (since $k-1<k$ , our hypothesis is true.)
So for the $Y$ in cyan we have: $|Y|\leq 2^{k-1} \tag1$
Again for the $X$ in red we have: $|X|\leq 2^{k-1} \tag2$
Adding $(1) and (2)$ we have,
$$|Y|+|X|\leq 2.2^{k-1} \implies n \leq 2^{k}$$
Now we can assume the edges from $X$ to $Y$ to be present now, and the $G_k$ looks like this
Union of this with the previous fig, gives $K_n$
Conversely, suppose that $n \leq 2^ k$ . We partition the vertex set into subsets $X$, $Y$, each of size at most $2^{k-l}$. By the induction hypothesis, we can cover the complete subgraph induced by either subset with $k - 1$ bipartite subgraphs. The union of the $i$th such subgraph on $X$ with the $i$th such subgraph on $Y$ is a bipartite graph. Hence we obtain $k - 1$ bipartite graphs whose union consists of the complete subgraphs induced by $X$ and $Y$. The remaining edges are those of the biclique with bipartition $X$, $Y$. Letting this be the $k$th bipartite subgraph completes the construction.
Now for the converse let us assume the $n\leq 2^k$. Now suppose we divide the entire set of vertices into two parts ($X$ and $Y$) such that each is having a size of at most $2^{k-1}$, (like $\frac{n}{2}\leq \frac{2^k}{2}$). We were initially having a complete graph on $n$ vertices. Due to the partition we have two complete subgraphs of size $|X|$ and $|Y|$.
By the induction hypothesis, each of the the complete subgraphs $X$ or $Y$ has $k-1$ bipartite graphs.
Now if one does union of these two ($X$ and $Y$) it seems that we shall get $2^k$ bipartite graphs, but its not. Check the diagram below.
On combining the $i$th bipartite graphs of each we can get only $2^{k-1}$ bipartite graphs on unions.
After this if we add the edges between $X$ and $Y$ we shall get the $k$ th bipartite graph.