- #1
Terrell
- 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.
I would simply like to know how to get 2^k.
Terrell said:I would simply like to know how to get 2^k
i mean why it is like this.QuantumQuest said:Do you mean why is it like this or how to pick them as a step in the induction needed?
Terrell said:i mean why it is like this
Terrell said: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
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.QuantumQuest said: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?
To calculate 2^k, simply raise 2 to the power of k. In other words, multiply 2 by itself k times. For example, if k=3, then 2^k = 2*2*2 = 8.
Yes, most calculators have a power function that allows you to easily find 2^k. Look for a button that says "x^y" or "^" and enter 2 and then the value of k.
The value of 2^0 is 1. This is because any number raised to the power of 0 is equal to 1.
2^k can be represented in exponential form as 2^k = 2k. The number in the superscript (k) represents the power to which 2 is raised.
Yes, you can use negative values for k in 2^k. This results in a fraction or a decimal number. For example, 2^-1 = 1/2 or 0.5.