The maximum number of edges in a planar graph.

Published On :2022-03-31 11:29:00

 We want to find the maximum number of edges in a planar graph G with n vertices. 

Clearly, when the number of edges is maximum & G is a plane graph, then each face of G must be a triangle. Otherwise, we would be able to add more edges. 

Let G be such a graph ( faces have three edges ) with n vertices, q edges & f faces. Since each face of G has a boundary of three edges and each edge is exactly two faces, it follows that 2q = 3f.

 In Eular's formula n - q + f = 2, substitute f=2q/3 to get 

n - q + 2q/3 = 2

then 

3n - 3q + 2q = 6 

q = 3n - 6

So, for all planar graphs, we get q =< 3n - 6  ( n >= 3 ).

This gives a necessary condition for planarity. we state it in the following theorem.

Theorem: If G is a planar graph with n vertices  ( n >= 3 ) and q edges, then 

q =< 3n - 6.

Ex: Show that K5 is nonplanar?

Sol: In K5, n = 5, q = 10 & using previous theorem if K5 is planar, then 

q =< 3n - 6

10 =< 3(5) - 6 = 9

Thus K5 is nonplanar.

Corollary: Kn (n >= 5 ) is nonplanar.