Corolary of Euler's identity Theorem in planar graphs

27 Views Asked by At

This is a corollary of the book "Graphs and Digraphs" (Chartrand). I just posted for you to evaluate my proof and to let me know what do you think. Thanks!

If $G$ is a plane graph with $n$ vertices, $m$ edges and $r$ regions, then $n - m + r = 1 + k(G)$. Where $k(G)$ denotes the number of connected components of $G$.

1

There are 1 best solutions below

0
On

Proof.

We have two cases:

  1. If $G$ is connected, $k(G)=1$ and by Euler's identity theorem we have $n-m+r=2=1+1=1+k(G)$ which holds.

  2. If $G$ is disconnected, then $k(G)>1$. Let $G1, G2, \ldots, G_{k(G)}$ be the components of G and let $n_i, m_i, r_i$ be the respective order, size and number of regions of the i-th component $G_i$. Since $r_i$ is always considering the external region for each component, we have: $n-m+r=\sum_{i=1}^{k(G)}n_i - \sum_{i=1}^{k(G)}m_i + (\sum_{i=1}^{k(G)}r_i-1)+1$. Note that we are subtracting 1 to each $r_i$ and adding 1 to the general sum because we just want to count the exterior region once. Therefore we have $n-m+r=(\sum_{i=1}^{k(G)}n_i - m_i + r_i ) - \sum_{i=1}^{k(G)}1+1$, and by Euler's identity Theorem, $n-m+r=2k(G) - k(G)+1=1 + k(G)$. $\blacksquare$