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.
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.