Number of edges in a planar graph where each face is incident to four edges.

Question

Let $G$ be a planar graph with $n$ vertices and an embedding where each face is incident to exactly four edges. What is the number of edges in the graph?

Answer 1

If you're not satisfied with the argument using $2F=E$ given in the comments (which is essentialy a counting argument, since each edge is bounded by exactly 2 faces, so the faces are overcounted by a factor of $2$, with one exceptional case when there is 4 edges incident to 1 face), you can instead look at the dual graph and use the handshaking lemma, because you know the degree of every vertex in the dual graph.

Let $V$, $E$ and $F$ be the number of vertices, edges and faces of $G$, respectively. Since $G$ is planar, it has a well defined dual graph $G^*$. The dual graph $G^*$ has $F$ vertices, $E$ edges and $V$ faces. From the Euler-Poincare formula we find that $G^*$ has $$F=2-V+E$$ vertices. Because every face of $G$ is bounded by $4$ edges, every vertex of $G^*$ will be of degree $4$. Therefore, from the handshake lemma we obtain $$2E=\sum_{v^* \text{ a vertex of }G^*}\deg v^*=4(2-V+E),$$ which after simplifying becomes $$E=2V-4.$$

However, this formula does not account for trees with $4$ edges. So if $F=1$, there can be exactly $n=5$ vertices, or $F>1$ and $E=2V-4$.

It is often a convention to count the edges of a tree twice when talking about edge-face incidence (but in that case the language of half-edges is more appropriate). If you're working with that convention in place, then $E=2V-4$ covers trees as well, but each edge that is bounded by a single face must be counted twice.