0
$\begingroup$

Is it possible to find an upper bound for the number of edges in a simple planar graph with n vertices?

To be more specific, if we represent the number of vertices and number of edges as an ordered pair, then $(3,3), (4,6), (5,9)$ have planar representations. What is the highest number of edges for which a graph with 6 vertices have a planar representation? Is it possible to generalise this to n vertices?

|cite|improve this question
$\endgroup$
1
$\begingroup$

The maximum number of edges in a planar graph with $n$ vertices is achieved when every face is a triangle.

In this case $2E=3F$ by double counting.

Plugging into Euler's Formula gives:

$n-E+F=2\implies n-E+\frac{2E}{3}=2\implies n-2=\frac{E}{3}\implies E=3n-6$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ That's true for $n \ge 3$ only. $\endgroup$ – Smylic Jun 15 '17 at 13:36
  • $\begingroup$ good point, for $n=1$ the max is $1$ and for $n=2$ the max is $1$. $\endgroup$ – Jorge Fernández Hidalgo Jun 15 '17 at 13:38
  • $\begingroup$ The part that every face needs to be a triangle appeals to me intuitively. Is there an argument to make it rigorous? $\endgroup$ – Hikaru Jun 15 '17 at 13:44
  • 2
    $\begingroup$ suppose that a face has more than three vertices, then you can add one of the internal edges (a chord inside the face) and have more edges. $\endgroup$ – Jorge Fernández Hidalgo Jun 15 '17 at 13:45
  • 1
    $\begingroup$ @Hikaru: The part about adding an extra chord is a little bit more delicate though, as not any chord works, some of them may already be edges inside the graph. But it is not hard to show that at least one of them must be unused. Because if chord $ab$ was already inside the graph then you can pick two vertices on two different sides with respect to $ab$. $\endgroup$ – Jorge Fernández Hidalgo Jun 15 '17 at 13:52
0
$\begingroup$

I did a 3 step thought process to visualize Jorge's answer:

  1. place the vertices in a circle (n-1 edges)
  2. connect one vertex to all others from inside the circle (n-2) edges
  3. connect one vertex to all others with vertices going around the circle (n-3 edges)

if you add it all up you get $$|E|=3n-6 $$

|cite|improve this answer
$\endgroup$

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.