6
$\begingroup$

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!

$\endgroup$
6
  • 5
    $\begingroup$ In the situation you describe, it would be customary to count the edge from the centre twice, because "both its sides are in the same region". To put this more precisely, in counting the edges surrounding a region, we count the length of the smallest circuit containing all edges which bound the region, and this forces such an edge to be counted twice. $\endgroup$
    – David
    Jun 23, 2014 at 11:35
  • $\begingroup$ If I assume correctly that you are talking about length of each Face, then it is true for every planar graph that the sum of the lengths is $2|E|$. Easy to prove using the dual graph and degree-sum formula. $\endgroup$ Jun 23, 2014 at 11:37
  • 3
    $\begingroup$ You cannot get a circuit, that is, returning to the starting vertex, unless you use the "inner" edge twice. Not sure about the $\le$, perhaps you could post an example. $\endgroup$
    – David
    Jun 23, 2014 at 11:44
  • 1
    $\begingroup$ I actually can't find any online. It only says so in my notebook where we proved that $m \le 3n-6$. Also in proofs like these: cimpa-icpam.org/IMG/pdf/BandungRyan5.pdf They word it like this: "Each edge has two sides so it contributes exactly 2 to the sum of the face degrees." even though that's not strictly true because an "inner" edge doesn't really have two sides. But if we count it the way you described (circuits) I now see why it's counted twice.. thanks! $\endgroup$
    – Cauthon
    Jun 23, 2014 at 11:53
  • 2
    $\begingroup$ The discussion of lengths of faces always counts it so - the length of a face is the total length of the closed walk(s) bounding the face, so on a single edge you would've to go forward and backwards. $\endgroup$ Jun 23, 2014 at 11:55

1 Answer 1

-1
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.