So I'm confused even though this is supposed to be simple:
From what I understand, in a planar graph, if we count the edges of each face, we should get $\sum F_t \le 2|E|$ because an edge can separate maximum 2 faces, no more.
However, in many proofs about different qualities of planar graphs, I see the statement that each esge is counted exactly twice, i.e. $\sum F_t = 2|E|$. I know that this is true specifically if all faces are polygons. But if we draw a box, and then another edge from its center to one of its corners, it's a planar graph and the inner edge is only counted once.
Any clarification of when is $\sum F_t = 2|E|$ true vs when $\sum F_t \le 2|E|$ would be great. Thanks!
Best Answer
I found counting edge/faces this way very confusing. For example there are arguments such as: "there are at least 3 edges bounding a face and at most two faces sharing an edge then $3 | F| \le 2 | E|$". I assume that for $\sum_t F_t$ you mean |F|, the total number of faces in the graph $\Gamma(V,F)$. I do not see the $3 | F | \le 2 | E |$ obvious from the the "least" and "most" edge/faces statements above. Instead I prefer to put the problem in terms of triangles which are much simpler to understand. Any face can be decomposed in triangles. Another way (and this is direct and simpler) is shown at the end of this proof. This is based on adding all degrees (number of edges) for each face since they will count redundancies as well; then use that formula to link the number of edges with the number of faces in an inequality relationship. We prove:
Proposition: In a planar graph with two or more vertices, $3 |F| \le 2 |E| $.
Proof: We first assume that the faces are all triangles . For example for one face (besides the exterior face) $|E|=3$ and $F=2$ so the equality $6=6$ is achieved. However for two faces (for example a rectangle with a diagonal) we have $|E|=5$ and $|F|=3$, here the inequality $9<10$ is strict. We do this by induction over $|F|$ . We introduce a new face $|F|$ by adding one more vertex and two more edges (note that since all faces are triangles we can not add a new face in the interior of the graph). We need to show that $2|E+2| \ge 3|F+1|$. \begin{equation} 2 | E + 2| = 2 | E| + 4 \ge 3|F| + 4 \ge 3|F| + 3 \ge 3|F+1|. \end{equation}
Let us now assume that at least one face $f$ is not triangular. Then we can divide the face into two new faces $f_1$ and $f_2$ with the help of some "diagonal" edge and form a graph $\Gamma'(F',V')$ which is the original $\Gamma(F,V)$ with the new split face. We can then consider a partition of set $F'$ into $F'= F_1 \cup F_2$, such that $f_1 \in F_1$ and $f_2 \in F_2$. We apply an induction argument over the number $|F'|$. If $|F'|=2$, since a face has at least 3 edges then $2 | E | \ge 3 | F|$. Let us assume that the proposition is valid for any number $2 \le n \le | F|$. Since each graph $\Gamma_1(F_1, V_1)$, and $\Gamma_2(F_2, V_2)$ has less or equal number of faces than the graph $\Gamma'(F',V')$, we can apply the induction hypothesis to both $\Gamma_1$ and $\Gamma_2$. That is: \begin{equation} 2 |E_1 | \ge 3 | F_1 | \quad \quad \mathrm{and} \quad \quad 2 | E_2 | \ge 3 | F_2 |. \end{equation}
Now, $|E| = |E_1| + |E_2| -2 $ since the common edge was added twice, and $|F| = |F_1 | + | F_2| - 2 $ since the outside (infinite face) was counted twice and one more face was counted in the interior. Then \begin{eqnarray} 2 | E | &=& 2|E_1 | +2 |E_2| - 4 \\ &\ge& 3 |F_1| + 3 |F_2| -4 \quad \text{ by induction hypothesis} \\ &=& 3 | F_1 + F_2 - 2 | + 6 - 4 \\ &>&3 |F|. \end{eqnarray}
In fact there is a more direct and simpler way to prove this: Let us call $d(f_i)$ the degree of a face $f_i$. That is, the number of edges bounding that face. we observe that \begin{equation} \sum_i d(f_i) \le 2 |E| \quad \quad \quad (1) \end{equation} since each edge that is part of a face contributes to exactly two faces, then add all those edges that are not part of a face. On the other hand each face is bounded by at least 3 edges, so $\sum d(f_i) \ge 3|F|$, and using equation (1) we find that $2 |E| \ge 3 |F|$.
In general, and using exactly the same method and assuming that the minimum number of edges of a face in a graph is $g \; (g\ge3)$ then we can write \begin{equation} 2 | E| \ge g | F|. \end{equation}