- #1
- 317
- 26
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.
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?I would simply like to know how to get 2^k
i mean why it is like this.Do you mean why is it like this or how to pick them as a step in the induction needed?
As I remember from another thread you asked for the intuition ofi mean why it is like this
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
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.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?