# Prove $\overline{G}$ is not a planar graph

Let $$T = \left(V, E\right)$$ be a tree such that $$\left|V\left(T\right)\right| = 8$$. After adding $$2$$ edges to $$T$$, a simple graph $$G = \left(V^{'}, E^{'}\right)$$. I need to show that $$\overline{G} = \left(N, K\right)$$ is not planar. Is my proof correct?

Assume $$\overline{G}$$ is planar.

$$T$$ is a tree $$\Rightarrow \left|E\right| = 8 - 1 = 7 \Rightarrow \left|E^{'}\right| = 9$$. $$\left|E\left(K_8\right)\right| = \frac{8\cdot7}{2} = 28$$. Therefore, $$\left|K\right| = 28 - 9 = 19.$$ In a planar graph, $$e \le 3v - 6$$, an therefore $$19 \lt 3\cdot8 - 6 = 18$$ - contradiction. Therefore, $$\overline{G}$$ is not planar.

• Looks good to me. Sep 1, 2022 at 22:13

The claim you use in the proof is not correct. In a connected planar graph, $$e \le 3v-6$$. Remember that while proving this claim, you need to use Euler's formula, which is correct only on a $${\bf{connected}}$$ planar graph. Hence, you need to show that $$\overline{G}$$ is connected first.