# 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. –  audiFanatic Apr 16 '14 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. –  Casteels Apr 16 '14 at 14:47
Ah, ok; perfect! Thanks for the clear explanation! –  audiFanatic Apr 16 '14 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$.

-