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 largest n such that K_n can be expressed as the union of

  1. Apr 26, 2017 #1
    there's a proof provided, but i want to know the intuition as to why it is 2^k.
  2. jcsd
  3. Apr 26, 2017 #2


    User Avatar
    2017 Award

    Staff: Mentor

    I think there is something missing in the question.
  4. Apr 26, 2017 #3
    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
  5. Apr 26, 2017 #4
    Plug in some values,
    Draw some examples,
    Although it can't be done,
    Try to get some counter examples..
    And ah ha!
    In a moment or two,
    You'll get the intuition!
  6. Apr 26, 2017 #5


    User Avatar
    Gold Member

    ##K_n## is a complete graph and the theorem claims that this can be expressed as a union of ##k## bipartite graphs if and only if ##n\leq 2^k##.

    So, in order to get a more intuitive view, I'd advise to solve for ##k## and see the minimum number of bipartite graphs sufficient to cover ##K_n##.
    You can take some values for ##k## and see where it goes, doing some required representations along the way. The gist of the theorem is that if the inequality gets violated there can't be a coverage of ##K_n## with ##k## bipartite graphs.
  7. Apr 26, 2017 #6
    i did some calculations but it still just won't sit well with me. i did some research and found that there's 2^k colors since each bipartite graph have 2 colors and there are k such bipartite graphs. after some thinking, it became obvious that the number of vertices should be less than 2^k because each vertex can appear in more than one bipartite graph thus it can have more than 1 color. lastly, for the equality case, there are calculations that did satisfy that ,but i seem to lack the understanding as to why.
  8. Apr 29, 2017 #7
    It seems like you've hit the nail on the head: a graph can be represented as a union of k bipartite graphs if and only if it is 2^k-colorable.

    For one direction, say a graph is a union of k bipartite graphs. For each bipartite graph we can 2-color it. Then for the original graph, for each vertex we note what color it is in each of the bipartite graphs, and the final color is the ordered k-tuple of binary colors, so that is a 2^k-coloring. Going the other direction, if a graph is 2^k colorable, we can arbitrarily assign each of the 2^k colors to an ordered k-tuple of binary colors. Then we define the ith bipartite graph by saying vertices u and v are connected if and only if they are connected in the original graph and the ith members of their k-tuples are different. So the graph is a union of k bipartite graphs.

    I would say the intuition is basically the notion of product coloring; if I can color G with g colors and H with h colors, I can color the union with gh colors by looking at the product coloring. Repeating the process, if G_1, G_2, ..., G_k can be colored with g_1, g_2, ..., g_k colors, then the union of the G_i's can be colored with g_1 g_2 ... g_k colors by taking the product coloring.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted