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.

  • 2
    $\begingroup$ MathJax works in the title section too :) $\endgroup$ – Shaun Mar 2 at 21:14
  • 1
    $\begingroup$ @Shaun thank you for that! I will make the change:) $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Hidaw Mar 3 at 16:05
  • $\begingroup$ or am I missing something? $\endgroup$ – Hidaw Mar 3 at 16:15
  • 1
    $\begingroup$ The formula is also true for not connected graph. I added some details $\endgroup$ – Thomas Lesgourgues Mar 3 at 18:42
  • $\begingroup$ Thank you so very much! That is really helpful!! $\endgroup$ – Hidaw Mar 3 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.