Each edge of the complete graph with 11 vertices is colored either red or blue. We then look at the graph consisting of all red edges and the graph consisting of all blue edges. How do I show that at least ONE of these two graphs is not planar?
I know in every connected planar drawing of a graph |V| - |E| + F = 2. Any connected planar graph on |V| ≥ 3 vertices satisfies 3F ≤ 2|E| and |E| ≤ 3|V| - 6. How do I use this information to solve this problem? I am confused on where I should start.
Denote the graph $R$ colored in red and the graph $B$ colored in blue. Note that $R\cup B$ is the complete graph $K_{11}$. Suppose both of them are planar, then we have $$\tag{1}|E(R)|\leq 3|V(R)|-6\mbox{ and }|E(B)|\leq 3|V(B)|-6.$$ (Note that this formula is also true for planar graph which is not connected. To see this, simply apply the formula $|E|\leq 3|V|-6$ to each connected component.) Note that $|V(R)|=|V(B)|=11$ and $|E(R)|+|E(B)|={{11}\choose{2}}=55$, since $R\cup B=K_{11}$. Combining this with $(1)$, we obtain $$55=|E(R)|+|E(B)|\leq 3(|V(R)|+|V(B)|)-12=3\cdot 22-12=54$$ which is absurd. Therefore, one of them should be planar.