# 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

## 1 Answer

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.

• I have just come across a corollary in my Graph Theory book and it says that "If G is a connected planar graph with n >=3 vertices and m edges, then m<=3n-6. If additionally G has no triangles, then m<=2n-4.". So how can that be? – Hidaw Mar 3 at 16:05
• or am I missing something? – Hidaw Mar 3 at 16:15
• The formula is also true for not connected graph. I added some details – Thomas Lesgourgues Mar 3 at 18:42
• Thank you so very much! That is really helpful!! – Hidaw Mar 3 at 18:55