1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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 #1
    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. jcsd
  3. Jun 26, 2017 #2

    QuantumQuest

    User Avatar
    Gold Member

    Do you mean why is it like this or how to pick them as a step in the induction needed?
     
  4. Jun 28, 2017 #3
    i mean why it is like this.
     
  5. Jun 29, 2017 #4

    QuantumQuest

    User Avatar
    Gold Member

    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?
     
  6. Jul 1, 2017 #5
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: The complete graph K_n can be expressed as the union of k bipartite graphs iff n≤2^k
Loading...