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$$
Adding them all, we get,
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).
Best Answer
Your proof seems valid to me. This is exactly the approach I was going to take.