# Suppose that a planar graph has $k$ connected components, $e$ edges, and $v$ vertices. Also suppose that$\dots$

Question:
Suppose that a planar graph has $k$ connected components, $e$ edges, and $v$ vertices. Also suppose that the plane is divided into $r$ regions by a planar representation of the graph. Find a formula for $r$ in terms of $e, v,$ and $k$.

Attempt:
Let $r_i, v_i, e_i$ be the number of regions, edges, vertices in the $i^{th}$ connected component, thus

$$r_i = e_i - v_i + 2$$

Suppose we ignore the outer most regions for now, our new equation is,

$$r_i' = e_i - v_i + 2 - 1$$ $$= r_i' = e_i - v_i + 1$$

where $r_1' + r_2' + \dots r_k' = r''$; $e_1 + e_2 + \dots e_k = e$; $v_1 + v_2 + \dots v_k = v$, therefore

$$r_1' + r_2' + \dots + r_k' = \\r'' = e-v+k$$

Since $r''$ is deprived of any outer regions, we add one to reintroduce the outer region, thus $r = r'' + 1$,

$$r = e-v+k+1$$

Is that attempt correct? It seems too ad-hoc for me (I've never done or seen this pattern of solving problem before).

• Looks good to me. Your proof is an actual hidden induction by $k$, after you found the right formula, it might be easier to prove it directly by induction. – N. S. Aug 16 '14 at 18:40