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

[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.

 

[QuantumQuest]

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

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

 

[Terrell]

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

i mean why it is like this.

 

[QuantumQuest]

i mean why it is like this

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

The largest n such that K_n can be expressed as the union of bipartite graph is 2^k where k is the number of bipartite graphs

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?

 

[Terrell]

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?

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.