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