Theorem: The number of vertices $|V|$, edges $|E|$, and faces $|F|$ in an arbitrary connected planar graph are related by the formula $$|V|+|F|-|E|=2$$
Proof Attempt:
(For acyclic planar graphs) Let $G(V,E)$ be an acyclic graph. For any line-subgraph $L=(V',E')$ of $G$, we can easily verify that $|V'|=2$, $|E'|=1$, and $|F'|=1$ where $F'$ is the face of a line graph. Thus, $|V'|+|F'|-|E'|=2$. As we construct $G$ from $L$ by adding edges, note that for each edge we add, we add a vertex so for any number of edges $n\in\Bbb{N}$ we add, we also add $n$ vertices. Hence, $(|V'|+n)+|F'|-(|E'|+n)=|V|+|F|-|E|=2$.
(For planar graphs with cyclic subgraphs) The smallest planar graph with a cyclic subgraph is $C_3$(a triangle). Clearly, any planar graph with a cyclic subgraph can be constructed by adding more points and edges to $C_3$. We assert that to add an edge to $C_3$, we either
Add a point $v^*$ on an existing edge $l$ which 'splits' $l$ to two different edges then connect $v^*$ to an existing vertex with a new edge; this adds 2 edges, 1 vertex, and 1 face or
Connect two existing vertices, not connected by an edge, with a new edge; this adds a face or
Add 2 new vertices with each of them on an existing edge, then connect the two new vertices with a new edge; this adds 2 vertices, 1 face, and 3 edges.
Nevertheless, observe that method (1) and (3) above is a sequential combination of two very primitive steps:
Add a vertex to an existing edge.
Connect two existing vertices, not connected by an edge, with a new edge. (This is method (2) above.)
Note:
- Adding a point to an existing edge implies $|V|+1$, $|E|+1$, and $|F|+0$.
- Method 2 implies $|V|+0$, $|E|+1$, and $|F|+1$.
- Adding a point outside any edge forces us to connect this new vertex with an existing vertex by a new edge; this implies $|V|+1$, $|E|+1$, and $|F|+0$.
Hence, the form of numerical parameter variations occurring every time we construct a new connected planar graph is of the following:
- $(|V|+n)+|F|-(|E|+n)$
- $|V|+(|F|+m)-(|E|+m)$
Therefore, $|V|+|F|-|E|=2$.