# Prove that $G'$ is not planar.

Let $$G$$ simple connected graph on $$n$$ vertices and assume that both $$G$$ and $$G'$$(complement) are planar.

$$m$$ and $$m'$$ be the number of edges in $$G$$ and $$G$$.

$$m+m'$$ $$=$$ $$n(n-1)/2$$

$$m, m'$$ $$≤ 3n − 6$$

$$m+m' ≤6n−12$$

$$n(n−1)/2 =m+m' ≤6n−12$$

$$⇒$$ $$n^2 −13n+24≤0$$ $$⇒$$ $$n<11$$.

Would this be a correct solution?

I have also noticed this only works for connected graphs so I was wondering how would I expand it to disconnected graphs?

Any help would be really appreciated.

• MathJax works in the title section too :) – Shaun Mar 2 at 21:14
• @Shaun thank you for that! I will make the change:) – Hidaw Mar 2 at 21:30

This is ok. This works fine even for non connected graph. The formula $$m\leq 3n-6$$ is not restricted to connected graphs.
Edit The formula is true for connected or non connected graphs. Suppose that $$G$$ is a planar graph ($$m$$ edges, $$n$$ vertices), disconnected, with two connected component $$G_1$$ and $$G_2$$ with $$m_1$$ and $$m_2$$ edges, on $$n_1$$ and $$n_2$$ vertices. So that $$m=m_1+m_2$$ and $$n=n_1+n_2$$
Each graph $$G_1$$ and $$G_2$$ is planar. Take a vertice $$v_1$$ on the outer face of $$G_1$$ and $$v_2$$ on the outer face of $$G_2$$. Add an edge between $$v_1$$ and $$v_2$$, creating a planar connected graph with $$m_1+m_2+1$$ edges, on $$n_1+n_2$$ vertices. Therefore, using Euler's formula : $$m_1+m_2+1\leq 3(n_1+n_2) - 6$$ And $$m\leq 3n-7$$ In fact you can prove that if $$G$$ is made of $$k$$ connected components : $$m\leq 3n-5-k$$ The formula is even stronger for non-connected graph.