(a) Let G = (V,E) be a loop-free connected graph with | V | ≥ 11. Prove that either G or its complement must be nonplanar.
(b) The result in part (a) is actually true for | V | ≥ 9, but the proof for | V | = 9, 10, is much harder. Find a counterexample to part (a) for | V | = 8.