( Euler's Formula ) Let G be a connected plane graph with n vertices, q edges and f faces. Then n-q+f=2.

 

Theorem: ( Euler's Formula ) Let G be a connected plane graph with n vertices, q edges, and f faces. Then n - q +  f = 2.
Proof: 

Let T be a spanning tree of G. For any tree, we have q = n -1 , f = 1 and thus n - q - f = n-( n - 1 ) + = 2. 

Now, G can be obtained from T by adding edges. Each time we add edges. we create a new face. So, q & f are increased by one. Thus the value of n - q + f remains unchanged at 2 no matter how many new edges are added.

Corollary: Ler G be a plane graph with n vertices, q edges, f faces, and k components. Then n - q +  f = k + 1.

Ex: let G be a connected plane graph with order 10 and size 14. Find the number of faces in G.

Sol:
n - q +  f = 2
=> 10 - 14 + f = 2 
=> f = 6