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