there's a proof provided, but i want to know the intuition as to why it is 2^k.
I think there is something missing in the question.
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
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!
##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.
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.
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.
Separate names with a comma.