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?
Best Answer
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$