> [!theorem|*] Euler's Formula > If a planar graph $G$ has $n$ vertices, $m$ edges, and $f$ faces (including the unbounded one), then $n - m + f = 2.$ ### Bounds on the Number of Edges The central idea of bounding $m$ with $n$ follows from finding an inequality $f \le r m,$so substituting into Euler's formula gives $2 = n-m + f \le n - (1 - r)m,$so $m \le (n - 2) / (1-r)$. Let the faces be $\mathcal{F} =\{ F_{1},\dots, F_{f} \}$. The roughest bound comes from the fact that *each face has at least $3$ edges touching it*; the edges are either in a cycle (so only one side is in the face), or a bridge (both sides are the same face). Therefore with $e(F)$ be the number of edges on its boundary (counting the bridges twice), $3f \le \sum_{F \in \mathcal{F}}e(F)= 2m.$This gives the bound $m \le (n-2) / (1 - 2 / 3)=3n-6$. If $G$ contains no triangles, $e(F) \ge 4$, so the bound can be improved to be $4f \le \sum_{F \in \mathcal{F}}e(F) \le 2m,$giving the bound $m \le 2(n - 2)$. > [!examples] More complex examples > If $G$ contains triangles but no two triangles share an edge, let $t$ be the number of triangles. So $t$ of the faces have exactly $3$ edges, and $(f-t)$ have at least $4$. Therefore $3t + 4(f-t) \le 2m,$and use the fact that $t \le m /3$ (disjoint triangles need $3$ new edges per triangle) to find $4f \le 7m / 3$, so $m \le 12(n-2) / 5$.