Proving corollary to Euler's formula by induction

Question

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my textbook, Introduction to Graph Theory by Robin J. Wilson and the other comes from Kent University about half-way down the page. They essentially say the same thing, just slightly different wording, so I'll refer to the latter because it's online.

---

Specifically, I have an issue with this:

Corollary 1: Let $G$ be a connected planar simple graph with $n$ vertices, where $n ≥ 3$ and $m$ edges. Then $m ≤ 3n - 6$.

Proof: For graph $G$ with $f$ faces, it follows from the handshaking lemma for planar graph that $2m ≥ 3f$ (why?) because the degree of each face of a simple graph is at least 3), so $f ≤ \frac{2}{3} m$.

Combining this with Euler's formula

$$Since ~~~~~~~~ n - m + f = 2$$ $$We ~~get ~~~~~~~~~~ m - n + 2 ≤ 2/3 m$$ $$Hence ~~~~~~~ m ≤ 3n - 6.$$

---

My issue is that the proof seems to assume too much. It states that the degree of each face of a simple graph is at least 3. How can that be assumed? As far as I'm concerned, that's not necessarily true. Suppose you had the following graph, a simple tree. It is still planar, connected, and simple; so every requirement holds. Clearly there is just one face, the infinite face, and it is surrounded by just 2 edges; therefore it is not bounded by 3 or more edges as the proof claims. The degree of the infinite face is just 2 as far as I understand. Yet the corollary holds even for this graph. We get $ 2 \leq 3(3)-6$, which reduces to $ 2 \leq 3 $, which is valid. I'd appreciate if somebody could explain what's going on here. Thanks

---

One possibility I can think of is that since the infinite face touches both sides of the edges then it has degree 4 and not 2 as I mentioned earlier.

Answer 1

The linked-to notes were maybe a little unclear on this point, perhaps in the interest of not being too pedantic.

Anyway, for a given face $F$ of a connected plane graph, a boundary walk of $F$ is a closed walk that contains every edge on the boundary of $F$. This means that a boundary walk must start and stop at the same vertex.

The degree of a face is then defined to be the minimum possible length of a boundary walk of $F$.

So in your example, the infinite face actually has degree $4$, and I hope you can then convince yourself that if $n\geq 3$, any face has degree at least $3$.

Answer 2

Exactly, because the infinite face touches both sides of the edges it has degree $4$. Since these edges are bridges we must count them twice, once for each side. Planar graphs have the property that if $n\geq3$, then $2m\geq3f$.

Answer 3

Here, I've written two lemmas which have proof that is easily provable by induction. Then we combine them to observe the corollary

Lemma 1: For any embedding G' of any simple connected planar graph G,

$\sum_i{d(f_i)} = 2 e(G)$

Proof. Each edge contributes 1 to each face it is a bound, so it contributes 2 to the total sum.So the e(G) edges contributes 2e(G) to the total sum.

Lemma 2: For any simple connected planar graph G, with e(G) ≥3, the following holds:

e(G) ≤ 3n(G) - 6

Proof. Each face of any embedding G' of G is bounded by at least three edges, hence:

$\sum_i{d(f_i)} \ge 3f(G)$

From the above lemma,

$\sum_i{d(f_i)} = 2 e(G)$

hence: $ 2e(G) \ge 3f(G) \implies f(G) \le \frac{2}{3} e(G) $

From Euler's formula,

$n(G)+f(G) = e(G)+2$ ,

so

$n(G) + \frac{2}{3} e(G) \ge e(G) + 2 \implies \frac{1}{3} e(G) \le n(G) - 2 \implies e(G) \le 3n(G) - 6$