# I The complete graph K_n can be expressed as the union of k bipartite graphs iff n≤2^k

Tags:
1. Jun 26, 2017

### Terrell

The complete graph K_n can be expressed as the union of k bipartite graphs iff n≤2^k

I would simply like to know how to get 2^k.

2. Jun 26, 2017

### QuantumQuest

Do you mean why is it like this or how to pick them as a step in the induction needed?

3. Jun 28, 2017

### Terrell

i mean why it is like this.

4. Jun 29, 2017

### QuantumQuest

As I remember from another thread you asked for the intuition of

and you got some intuition using coloring. So now for the theorem you have to apply induction on $k$ ($n \geq 2$) in order to prove it.

Start from $k = 1$.Can you see the truth of the statement?
Proceed to $k = m$ for the inductive step. Hint: For $n \leq 2^{m+1}$ try to divide the vertices of $K_n$ in a helpful manner into two disjoint sets. Can you proceed further?

5. Jul 1, 2017

### Terrell

will take it from there. thanks! how do you know it was me? lol... will try proving it later on as i am working on something else. will make sure to get back to this thread.