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

• I
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
Gold Member
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
Gold Member
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.

QuantumQuest