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

  • #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.
 

Answers and Replies

  • #2
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
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?
 
  • Like
Likes Terrell
  • #3
317
26
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.
 
  • #4
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
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?
 
  • Like
Likes Terrell
  • #5
317
26
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.
 
  • Like
Likes QuantumQuest

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

Replies
6
Views
1K
  • Last Post
Replies
1
Views
5K
Replies
1
Views
676
Replies
5
Views
4K
  • Last Post
Replies
3
Views
1K
Replies
2
Views
476
Replies
3
Views
1K
Replies
9
Views
702
Replies
6
Views
3K
  • Last Post
Replies
23
Views
4K
Top