= Solution
For a finite connected <plane graph>, with $v$ <vertices>, $e$ <edges> and $f$ faces including the unbounded face, <Euler formula for a connected planar graph> is
$$
\boxed{v-e+f=2.}
$$
If the <graph> is a <tree>, $e=v-1$ and $f=1$. Otherwise remove an <edge> on a cycle. This preserves connectivity and joins the two faces on its sides, so both $e$ and $f$ decrease by one. Repeating reaches a <tree>, preserving $v-e+f$ throughout and proving the formula.
For a simple connected <graph> with $v\geq3$, each face boundary walk has length at least three, with bridges counted twice in the walk; the sum of lengths is $2e$. Hence $3f\leq2e$, which with Euler gives \b[$e\leq3v-6$]. If it has no <triangles in a graph>, no face boundary walk can have length three, and every boundary length is at least four. Thus $4f\leq2e$, giving
$$
\boxed{e\leq2v-4\quad\text{for a triangle-free planar graph with }v\geq3.}
$$
For a disconnected <graph>, add noncrossing bridges between its components; this preserves simplicity and creates no triangles, reducing to the connected bound.
Every <triangle-free> <planar graph> with at least three <vertices> has average degree $2e/v<4$, and therefore a <vertex> of degree at most three. Remove one such <vertex>. Its remaining <graph> is again <triangle-free> and planar. Induction, with <graphs> on at most two <vertices> as the base cases, provides a <graph colouring> with four colours of the remainder. At most three colours appear on the removed <vertex>'s neighbours, so a fourth colour extends the <graph colouring>. This proves \b[four-colourability without using the four-colour theorem].
Back to article page
