I was going through the text "Discrete Mathematics and its Applications " by Kenneth Rosen where I came across the proof of the Euler's Formula for a planar graph. Though they have explicitly considered simple planar connected graph, I hope the formula works even for planar connect graph which is not simple.(The later result can be achieved by including a few elementary cases for loops and parallel edges in the proof).
However the point which I felt like clarifying is the situation $1$ in the proof below where they assume that both of the edges are on the boundary of the region.
EULER’S FORMULA: Let $G$ be a connected planar simple graph with $e$ edges and $v$ vertices. Let $r$ be the number of regions in a planar representation of $G$. Then $r = e − v + 2$.
Proof: First, we specify a planar representation of $G$. We will prove the theorem by constructing sequence of subgraphs $G_1,G_2 ,...,G_e = G$, successively adding an edge at each stage. This is done using the following inductive definition. Arbitrarily pick one edge of $G$ to obtain $G_1$ Obtain $G_n$ from $G_{n−1}$ by arbitrarily adding an edge that is incident with a vertex already in $G_{n−1}$ adding the other vertex incident with this edge if it is not already in $G_{n−1}$ . This construction is possible because $G$ is connected. $G$ is obtained after $e$ edges are added. Let $r_n$ ,$e_n$ , and $v_n$ represent the number of regions, edges, and vertices of the planar representation of $G_n$ induced by the planar representation of $G$, respectively.
The proof will now proceed by induction. The relationship $r_1 = e_1 − v_1 + 2$ is true for $G_1$ , because $e_1=1,v_1=2$,and $r_1=1$.This is shown in Figure 1.
Figure 1
Now assume that $r_k = e_k − v_k + 2$. Let $\{a_{k+1},b_{k+1}\}$ be the edge that is added to $G_k$ to obtain $G_{k+1}$ . There are two possibilities to consider. In the first case, both $a_{k+1}$ and $b_{k+1}$ are already in $G_k$ . These two vertices must be on the boundary of a common region $R$, or else it would be impossible to add the edge $\{a_{k+1},b_{k+1}\}$ to $G_k$ without two edges crossing (and $G_{k+1}$ is planar). The addition of this new edge splits $R$ into two regions. Consequently, in this case, $r_{k+1} = r_{k} + 1,e_{k+1} = e_k + 1$, and $v_{k+1} = v_k$ . Thus, each side of the formula relating the number of regions, edges, and vertices increases by exactly one, so this formula is still true. In other words, $r_{k+1} = e_{k+1} − v_{k+1} + 2$. This case is illustrated in Figure 2(a).
Figure 2
In the second case, one of the two vertices of the new edge is not already in $G_k$ . Suppose that $a_{k+1}$ is in $G_k$ but that $b_{k+1}$ is not. Adding this new edge does not produce any new regions, because $b_{k+1}$ must be in a region that has $a_{k+1}$ on its boundary. Consequently, $r_{k+1} = r_k$ . Moreover, $e_{k+1} = e_k + 1$ and $v_{k+1} = v_k + 1$. Each side of the formula relating the number of regions, edges, and vertices remains the same, so the formula is still true. In other words, $r_{k+1} = e_{k+1} − v_{k+1} + 2$. This case is illustrated in Figure 2(b).
We have completed the induction argument.
Now few things which I felt worth clarification,when they are saying that, "In the first case, both $a_{k+1}$ and $b_{k+1}$ are already in $G_k$ . These two vertices must be on the boundary of a common region $R$".In situation 1 when they are considering vertices on the boundary of a region,I hope they are considering those vertices of type $b_{n+1}$ (in Figure 2(b)) to be part of the boundary of region as shown in Figure $3$. Or else another case has to be included having the same result as that of situation 1 but considering edges of the type just said. (The way I traced out the edge in figure 3, that is the method used even while finding the degree of a region)
Figure 3