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$.

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).

  • $\begingroup$ 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. $\endgroup$ – N. S. Aug 16 '14 at 18:40

Your proof seems valid to me. This is exactly the approach I was going to take.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.