I am trying to understand the proof of the theorem that says
The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n\leq2^k$
using the mathematical induction . Graph Theory by West gives the proof but I don't understand it. I need some one help me to understand it and simplify the proof step by step
I think the result should be $n\leq 2^k$. Suppose $K_n$ is a union of $k$ bipartite graphs $G_1,...,G_k$. Each of the $G_i$ gives a $2$-colouring of the vertices (say red/blue). For each vertex $v$, look at the set $R_v=\{i:v\text{ red in }G_i\}$. Now $R_v\neq R_w$, since there is an edge between $v$ and $w$ in some $G_i$, and then they have different colours in that $G_i$, so $i$ is in exactly one of the sets. There are $2^k$ possible sets, and all $n$ sets must be different, so $n\leq 2^k$.
From an assignment of sets to vertices where all vertices get different sets, you can work backwards to construct the $G_i$.