# Proving corollary to Euler's formula by induction

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.

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$.

• Ah, ok. So if the walk is not closed then I need to count each edge twice, right? But yes, once this information is clear I should be able to convince myself of that. Apr 16, 2014 at 14:39
• By definition, a boundary walk has to be closed. I think what you are thinking is that if you trace around the boundary of the face you'll encounter some edges which are bridges (edges whose deletion would disconnect the graph). These are the edges that need to be counted twice. Apr 16, 2014 at 14:47
• Ah, ok; perfect! Thanks for the clear explanation! Apr 16, 2014 at 14:49

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$.

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$$

• Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer./questions/5020/mathjax-basic-tutorial-and-quick-reference). Apr 16, 2019 at 5:31
• @dantopa are you a bot? Apr 16, 2019 at 5:35
• I hope not. How can I tell for sure? Apr 16, 2019 at 5:40
• @dantopa haha ok I thought you were auto welcoming bot I'd have understood you are if there would have been no response Apr 16, 2019 at 5:46
• @dantopa btw thanks for the welcome Apr 16, 2019 at 5:48