[proofplan] We reduce to the connected case (adding edges can only increase the edge count and cannot violate the target bound), then combine two ingredients. First, a double-counting bound on edge–face incidences: every face of a plane embedding of a graph with at least three vertices is bounded by at least $3$ edge-sides, and every edge contributes exactly $2$ edge-sides (one for each of its two adjacent faces), yielding $3F \le 2e(G)$. Second, [Euler's Formula](/theorems/2014): $|G| - e(G) + F = 2$. Solving for $F$ from Euler and substituting into $3F \le 2e(G)$ eliminates $F$ and rearranges to $e(G) \le 3|G| - 6$. [/proofplan] [step:Reduce to the case where $G$ is connected with a fixed planar embedding] Let $G$ be a planar graph with $n := |G| \ge 3$. If $G$ is disconnected, we can add edges between distinct components until $G$ becomes connected, preserving planarity (add one edge at a time between a pair of components, each time obtaining a planar graph with the same vertex set and strictly more edges). Let $G'$ be the resulting connected planar graph; then $e(G) \le e(G')$. If we prove $e(G') \le 3n - 6$, then $e(G) \le e(G') \le 3n - 6$. Hence, without loss of generality, assume $G$ is connected. Fix a planar embedding of $G$; write $m := e(G)$ and $F$ for the number of faces of the embedding. [guided] Why the reduction to the connected case works: adding an edge between two components of a planar graph can always be done while preserving planarity, because each component is drawn in the plane and we can route a new edge between any point of one component and any point of another without crossing existing edges (e.g., use the outer face of each component). After finitely many such additions, the graph is connected. Since the target bound $e \le 3n - 6$ depends only on $n$ and bounds $e$ from above, passing to the connected supergraph $G'$ gives the tightest bound; if that bound holds for $G'$, it certainly holds for $G$. One might worry whether different planar embeddings give different face counts. They do not for our argument: any connected planar graph satisfies [Euler's Formula](/theorems/2014) with the same value $n - m + F = 2$ for every embedding, so the resulting bound on $m$ is embedding-independent even though $F$ is technically embedding-dependent. [/guided] [/step] [step:Define face degrees and bound each face degree below by $3$] For each face $f$ of the embedding, define the **degree** $\deg(f)$ to be the number of edge-sides incident to $f$, counted with multiplicity: traverse the boundary walk of $f$ and count each edge traversal. An edge traversed twice (which happens iff the edge is a bridge whose two sides both lie in $f$) contributes $2$ to $\deg(f)$. We claim that $\deg(f) \ge 3$ for every face $f$. Suppose for contradiction that $\deg(f) \le 2$ for some face $f$. Case $\deg(f) = 0$: the boundary walk of $f$ is empty, so $f$ is a connected component of $\mathbb{R}^2$ with no graph boundary. This forces $G$ to have no edges at all, contradicting $n \ge 3$ combined with connectedness (a connected graph on $n \ge 2$ vertices must have at least one edge). Case $\deg(f) = 1$: the boundary walk traverses a single edge once. This is geometrically impossible in a simple graph: an edge $\{u, v\}$ with $u \ne v$ has two sides, each of which is part of the boundary of some face; a face with a single edge-side traversal in its boundary walk would require the edge to appear only once around it, but the closed boundary walk of a face must return to its starting vertex, forcing at least the two endpoints and hence a walk of length $\ge 2$. Case $\deg(f) = 2$: the boundary walk has length $2$, traversing either one edge twice (a bridge whose removal would disconnect $G$ into two components, but then $n \ge 3$ and connectedness force one of the components to contribute more edges to the boundary, contradiction) or two distinct edges between the same pair of vertices (a multi-edge, impossible in a simple graph) or two edges forming a degenerate $2$-cycle between two distinct vertices (again requires multi-edges). In a simple graph with $n \ge 3$ and connected underlying structure, every face is bounded by a closed walk of length at least $3$. Therefore $\deg(f) \ge 3$ for every face $f$. [guided] The lower bound $\deg(f) \ge 3$ is the place where the hypothesis $n \ge 3$ is used. For $n = 1$, the unique plane graph is a single vertex, which has one face (the whole punctured plane) of degree $0$; for $n = 2$ with a single edge, the unique face has degree $2$ (the edge is a bridge, traversed twice around the single face). Neither satisfies the bound $\deg(f) \ge 3$. For $n \ge 3$ in a simple planar graph, the boundary walk of every face is a closed walk of length at least $3$. Intuitively: a face with boundary of length $1$ would require a loop, and a face with boundary of length $2$ would require either a multi-edge (two edges between the same pair of vertices) or a bridge whose removal isolates a single vertex. Simple graphs forbid loops and multi-edges, and for $n \ge 3$ with connectedness, no such bridge configuration can bound a face. A cleaner way to see this for $2$-connected plane graphs is that every face is bounded by a cycle, so $\deg(f) \ge 3$ follows immediately from the fact that the shortest cycle in a simple graph has length at least $3$. The general argument given above handles the subtleties introduced by bridges in graphs that are not $2$-connected. [/guided] [/step] [step:Double-count edge–face incidences to get $3F \le 2e(G)$] Sum the face degrees over all faces: \begin{align*} \sum_{f} \deg(f) = \sum_{f} \#\{\text{edge-sides incident to } f\}. \end{align*} Reversing the order of summation, every edge $e \in E(G)$ has exactly two sides, each of which is incident to exactly one face. Hence every edge contributes exactly $2$ to $\sum_f \deg(f)$: \begin{align*} \sum_{f} \deg(f) = 2 e(G). \end{align*} Combining with the lower bound $\deg(f) \ge 3$ from the previous step: \begin{align*} 3 F \le \sum_{f} \deg(f) = 2 e(G). \end{align*} Dividing by $3$: \begin{align*} F \le \frac{2}{3} e(G). \end{align*} [guided] The double counting is the arithmetic heart of the argument. Counting pairs $(e, f)$ where edge $e$ is on the boundary of face $f$: \begin{itemize} \item Grouped by face: each face $f$ contributes $\deg(f)$ pairs, so the total is $\sum_f \deg(f)$. \item Grouped by edge: each edge has exactly two sides, and each side faces into exactly one face. A bridge has both sides in the same face (contributing $2$ pairs for that face); a non-bridge has its two sides in two distinct faces (contributing $1$ pair to each). Either way, each edge contributes exactly $2$ pairs. \end{itemize} Equating the two counts gives $\sum_f \deg(f) = 2 e(G)$. The face-degree lower bound $\deg(f) \ge 3$ then gives $3 F \le 2 e(G)$. This is the standard "pigeonhole for planar graphs" — one of the two facts, together with Euler's formula, from which most elementary planar bounds follow. [/guided] [/step] [step:Apply Euler's formula and rearrange to $e(G) \le 3|G| - 6$] Since $G$ is a connected plane graph, by [Euler's Formula](/theorems/2014): \begin{align*} n - m + F = 2, \qquad \text{i.e.,} \qquad F = 2 - n + m. \end{align*} Substituting into the bound $F \le \frac{2}{3} m$: \begin{align*} 2 - n + m \le \frac{2}{3} m. \end{align*} Multiply through by $3$: \begin{align*} 6 - 3n + 3m \le 2m. \end{align*} Rearranging: \begin{align*} m \le 3n - 6. \end{align*} Since $n = |G|$ and $m = e(G)$, this is $e(G) \le 3|G| - 6$, which is the desired bound. [guided] The final step is pure algebra. Euler's formula is used to **eliminate** $F$ from the inequality $3F \le 2e(G)$: $F$ is a quantity depending on the embedding, but the combination $F = 2 - n + m$ expresses it in terms of the vertex and edge counts, which are intrinsic. After substitution, the inequality is $3(2 - n + m) \le 2m$, which rearranges to $m \le 3n - 6$ — a bound that depends only on the graph, not on the embedding. This is consistent with the fact that the bound $e(G) \le 3|G| - 6$ is a statement about planar graphs (existence of *some* planar embedding), not plane graphs (a specific embedding). Note the sharpness: the bound $e(G) \le 3n - 6$ is attained by **triangulations** — simple planar graphs in which every face is a triangle. In that case $\deg(f) = 3$ for every face, so $3F = 2m$ exactly, and the derivation above becomes a chain of equalities. The complete graph $K_4$ (a tetrahedron boundary) is the smallest triangulation: $n = 4$, $m = 6 = 3 \cdot 4 - 6$. [/guided] [/step]