$K_n$ as an union of bipartite graphs Theorem: The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n \leq 2^k.$
I would appreciate a pedagogical explanation of the theorem. Graph Theory by West gives the proof but I don't understand it. Also this referece has the proof, but it kills me with the dyadic expansion argument.
Also, I don't see why $n \leq 2^k$, since the complete graph I can make it from the union of disjoint $K_{1,1}$ bipartite graphs, for instance. I just need $n(n-1)/2$ of such $K_{1,1}$.
 A: In your example you’re taking $k=\frac12n(n-1)$. For this $k$ it’s certainly true that $n\le 2^k$; in fact, if $n\ge 3$, $\frac12n(n-1)\ge n$, so $2^k\ge 2^n>n$. Thus, your example is entirely consistent with the result in question.
The point of the theorem is that (1) if $n\le 2^k$, then you can cover $K_n$ with $k$ bipartite graphs, but (2) if $n>2^k$, then you cannot do so. Since it’s $n$ that’s known and $k$ that we’re interested in, it might be more intuitive to solve these inequalities for $k$ in terms of $n$:


*

*if $k\ge\lceil\log_2n\rceil$, then you can cover $K_n$ with $k$ bipartite graphs, but  

*if $k<\lceil\log_2n\rceil$, then you cannot.


In other words, $\lceil\log_2n\rceil$ is the smallest number of bipartite graphs that are sufficient to cover $K_n$: no smaller number will do the trick.
The proof in Bollobás’s book is more straightforward than it probably looks; I’ll just expand it with a bit of extra explanation. The first point is that if $k$ bipartite graphs are enough to cover $K_{2^k}$, then $k$ bipartite graphs are enough to cover $K_n$ for any $n\le 2^k$. To see this, just note that if $n\le 2^k$, then $K_n$ is a subgraph of $K_{2^k}$, so any covering of $K_{2^k}$ by bipartite graphs automatically yields one of $K_n$ as well. 
Now label the $2^k$ vertices of $K_{2^k}$ with the $2^k$ possible sequences of $k$ zeroes and ones. 

For example, if $k=3$, the $2^3=8$ vertices are labelled $000,001,010,011,100,101,110$, and $111$. These strings are just the binary (base two) representations of the integers $0,1,\ldots,7$, padded where necessary with leading zeroes to make their lengths uniformly $3$.

Thus, if the vertices are $v_0,v_1,\ldots,v_{2^k-1}$, we label vertex $v_i$ with the $k$-digit binary representation of the integer $i$; we can write that string $b_1^{(i)}b_2^{(i)}\ldots b_k^{(i)}$. 

In the $k=3$ example, $v_5$ is labelled $101$, so $b_1^{(5)}=1$, $b_2^{(5)}=0$, and $b_3^{(5)}=1$.

Now let $\ell$ be any index between $1$ and $k$ inclusive. Let 
$$U_\ell=\left\{v_i:b_\ell^{(i)}=0\right\}\;,$$
the set of vertices whose labels have a $0$ in position $\ell$, and let
$$V_\ell=\left\{v_i:b_\ell^{(i)}=1\right\}\,$$
the set of vertices whose labels have a $1$ in position $\ell$. Clearly these two sets of vertices are disjoint. Let $G_\ell$ be the complete bipartite graph whose parts are the sets $U_\ell$ and $V_\ell$: the vertex set of $G_\ell$ is $U_\ell\cup V_\ell$, and the edges of $G_\ell$ are all of the pairs $\{u,v\}$ with $u\in U_\ell$ and $v\in V_\ell$.
$G_1,G_2,\ldots,G_k$ are then $k$ bipartite subgraphs of $K_{2^k}$, and I claim that they cover $K_{2^k}$. To see this, let $v_i$ and $v_j$ be any two distinct vertices of $K_{2^k}$. Then $v_i$ and $v_j$ have different labels $b_1^{(i)}b_2^{(i)}\ldots b_k^{(i)}$ and $b_1^{(j)}b_2^{(j)}\ldots b_k^{(j)}$. Since the labels are different, there must be an index $\ell$ such that $b_\ell^{(i)}\ne b_\ell^{(j)}$. Thus one of $v_i$ and $v_j$ is in $U_\ell$, the other is in $V_\ell$, and the edge $\{v_i,v_j\}$ of $K_{2^k}$ is in $G_\ell$.
This shows the first bullet point above. To show the second bullet point, it’s enough to show that $K_{2^k+1}$ cannot be covered by $k$ bipartite graphs for any $k\ge 0$. Suppose that this is false, and let $k$ be the smallest non-negative integers such that $K_{2^k+1}$ can be covered by $k$ bipartite graphs; we want to derive a contradiction. For future reference note that $K_{2^0+1}=K_2$ cannot be covered by $0$ bipartite graphs, so $k>0$. 
Let $G_1,\ldots,G_k$ be bipartite graphs covering $K_{2^k+1}$. For $\ell=1,\ldots,k$ let the disjoint vertex sets of $G_\ell$ be $U_\ell$ and $V_\ell$. Note that we may assume that $U_\ell\cup V_\ell$ is the entire vertex set of $K_{2^k+1}$. If not, just throw all of the unused vertices into $U_\ell$: the resulting graph is still bipartite and has exactly the same edges. $2^k+1$ is an odd number, so the $2^k+1$ vertices cannot be split into two sets of the same size: one of the sets $U_k$ and $V_k$ must contain over half of the vertices. Say that $U_k$ does. Then $U_k$ contains at least $2^{k-1}+1$ vertices, and $G_k$ does not contain any of the edges between these vertices. This means that all of the edges between these $2^{k-1}+1$ vertices must be covered by the $k-1$ bipartite graphs $G_1,\ldots,G_{k-1}$. In other words, we have a copy of $K_{2^{k-1}+1}$ that is covered by $k-1$ bipartite graphs. But $k$ was chosen to be the smallest non-negative integer for which this is possible, so we have our contradiction.
A: *

*Proof that $\lceil \log_2 n \rceil$ bipartite graphs suffices.
We label the vertices $\{0,1,\ldots,n\}$.  For $i \in \{1,2,\ldots,\lceil \log_2 n \rceil\}$ we define the $t$-th bipartite graph to contain the complete bipartite graph with vertex bipartition $A \cup B$ with $A$ containing the vertices with $t$-th bit $1$, and $B$ containing the vertices with $t$-th bit $0$.  In this way, if vertices $i$ and $j$ disagree at the $t$-th bit, then the edge $ij$ belongs to the $t$-th bipartite graph (and if $i \neq j$, then they disagree at some bit).
(We may delete edges that appear in multiple bipartite graphs.  It doesn't change anything.)

*Proof that $\lceil \log_2 n \rceil$ bipartite graphs is necessary.
If $(A_t \cup B_t)_{t=1}^k$ is the sequence of vertex bipartitions of the bipartite subgraphs that cover $K_n$, then for each vertex $v$ we assign it a non-negative integer label with $t$-th bit equal to $1$ is $v$ belongs to $A_t$ and $0$ if $v$ belongs to $B_t$.  There are $\leq 2^k$ such labels.
For an edge $ij$ to be covered, there must be some $t$ for which $i \in A_t$ and $j \in B_t$, or $i \in B_t$ and $j \in A_t$.  Consequently, $i$ and $j$ must receive distinct labels.  Thus, to have enough labels, we must have $2^k \geq n$.
