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