0
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

0
$\begingroup$

You are almost there, but not correct.

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .