Let G be a planar graph with k components Prove that n q r

Let G be a planar graph with k components. Prove that
n q + r = 1+k.

Solution

We are given that G has k components.

Let no. of vertices be n, no. of edges be q, no. of faces be r.

For every i [k] let component C_i has n_i vertices, q_i edges, and r_i faces.

Since G is planar graph so each and every vertices are connected, and so by Euler’s Formula, we can say,

for all i [k], n_i q_i + r_i = 2.

Adding these k equations we get: n₁ + · · · + n_k (q₁ + · · · + q_k) + (r₁ + · · · + r_k) = 2k.

Substituting n₁ + · · · + n_k = n, q₁ + · · · + q_k = q and r₁ + · · · + r_k = r + k - 1, gives

n - q + r + k - 1 = 2k

=> n - q + r = k + 1.