Plane Graphs, Euler's Formula and the Five Colour Theorem

A ray direction is bad if its line through $x$ contains a polygon vertex or is parallel to an edge line. There are only finitely many such directions. By [L2], [L1] applies in $\mathbb{R}$ and supplies a rational-slope direction in an open angular interval avoiding them.

In the chosen direction the ray misses every vertex and is not parallel to any edge. It therefore meets each closed edge segment in at most one point, and every such intersection is transverse. Since the polygon has finitely many edges, the total intersection set is finite and has the required properties.

Fix a general-position ray from $x$. The finite intersection points have positive distance from every polygon vertex and from every nonincident edge; transversality also supplies a positive angle at each crossing. Taking the minimum of finitely many positive tolerances gives a ball about $x$ in which parallel translated rays retain exactly these crossings.

Rotate one general-position ray continuously to another, avoiding the finitely many exceptional directions except at isolated parameters. Crossing an edge tangentially creates or destroys two intersections, while passing a polygon vertex transfers the intersection from one incident edge to the other or changes the count by two. Thus the count modulo two never changes, so parity is independent of the chosen ray.

Steps 1.1 and 1.2 make parity locally constant on the complement. A locally constant map to the discrete set $\{0,1\}$ is constant on each connected component, hence on each complementary region.

By [L1], the even and odd crossing classes are disjoint open unions of complementary regions. A point outside a large rectangle containing $P$ has a ray missing $P$ and hence even parity. Points sufficiently close to the two sides of the relative interior of any polygon edge have parities differing by one, so both classes are nonempty.

Let $x,y$ have equal parity. By [L2], begin with a polygonal path in the plane and perturb it to meet $P$ transversely at finitely many nonvertex points. Its number of crossings is even, because the parity changes once at each transverse crossing and agrees at the endpoints. Pair consecutive crossings along the path; for each pair, replace the intervening segment by a sufficiently close polygonal offset of one of the two polygon arcs between the crossing points. Finite, successively smaller disjoint neighbourhoods make all replacements avoid $P$. The resulting polygonal path joins $x$ to $y$ in the complement.

Step 2.1 shows each parity class is connected, while step 1.1 shows both are nonempty and no connected subset meets both. They are therefore exactly the two regions. The even class contains the exterior of a large rectangle and is unbounded; the odd class lies inside that rectangle and is bounded.

At every point of an edge interior, arbitrarily small points on its two local sides have opposite parity. The same holds at vertices by using the two incident edges and a small sector. Thus every point of $P$ lies in the frontier of both regions. Conversely, local constancy in [L1] gives every point off $P$ a neighbourhood contained in one region, so no such point lies in either frontier. Hence both frontiers equal $P$.

Complete $A$ to a polygon $P=A\cup B$, where $B$ is a polygonal arc with the same endpoints as $A$, has no other point in common with $A$, and avoids $x,y$. To construct $B$, take a sufficiently thin polygonal regular neighbourhood of the finite arc $A$: disjoint small vertex neighbourhoods joined by narrow strips along the edge interiors form a polygonal disk, and either boundary chain, capped to the two endpoints, supplies $B$. General position permits the finitely many boundary vertices to avoid $x,y$.

By [L1], $P$ has regions $U$ and $V$. If $x,y$ lie in the same region, polygonal connectedness of open components joins them there. If they lie in opposite regions, choose a point $z$ in the relative interior of $B$. A sufficiently short segment transverse to $B$ at $z$ has one endpoint $z_U$ in $U$ and the other $z_V$ in $V$. Join $x$ to the endpoint on its side and $y$ to the other by polygonal paths within those regions, then concatenate those paths with $z_U-z-z_V$.

The paths in step 2.1 avoid all of $P$ except possibly at $z\in B$, and $B\cap A$ consists only of the two common endpoints, so the concatenated path avoids $A$. Since $x,y$ were arbitrary, ${\mathbb{R}}^2\setminus A$ is polygonally connected.

The finite union of bounded line segments lies in a sufficiently large rectangle. The exterior of that rectangle is connected and disjoint from the drawing, so it lies in one face; every unbounded face must meet the exterior and hence equals that face. Thus there is exactly one unbounded face.

Add the edge arcs one at a time. An arc that does not close a cycle can be exposed inside one existing face and, by [L2], does not split it. An arc that closes a polygon lies in one existing face and, by [L1], splits that face into exactly two. Isolated vertices likewise do not disconnect a plane region. Each addition therefore changes the face count by at most one.

Starting from the empty drawing with one face, finitely many additions yield finitely many faces, and step 1.1 identifies exactly one as unbounded.

Since the drawing of $H$ is contained in the drawing of $G$, its complement contains the complement of $G$. The face $f_G$ is connected and lies wholly in the complement of $H$.

Choose a point of $f_G\cap f_H$. Both sets contain it, and [L1] says $f_H$ is the largest connected subset of the complement of $H$ containing it. Step 1.1 therefore gives $f_G\subseteq f_H$.

If $e$ lies on a cycle, the remaining edges of that cycle form a $u$-$v$ path in $G-e$. Every path in $G$ that used $e$ can replace that occurrence by this path, so deleting $e$ separates no formerly connected pair. Thus $e$ is not a bridge.

Conversely, if $e$ is not a bridge, $u$ and $v$ remain in the same component of $G-e$ and hence are joined there by a path. Adding $e$ to that path gives a cycle containing $e$.

Step 1.1 says an edge on a cycle is not a bridge, and step 1.2 says an edge not a bridge lies on a cycle. Taking the contrapositive of either implication and combining them proves the biconditional componentwise, including when $G$ is disconnected.

A sufficiently small rectangle about any interior point of $e$ meets the drawing only in a straight subsegment of $e$. Its two open half-rectangles lie in faces. Sliding overlapping rectangles along the compact edge interior shows that each local side remains in one face until an endpoint is reached; hence frontier membership propagates along the entire edge.

If $e$ lies on a cycle $C$, [L1] gives two regions of the polygonal image of $C$. The two local sides of $e$ lie in different such regions and cannot be joined in the complement of the full drawing, so they belong to two distinct faces of $G$.

If $e$ lies on no cycle, [L2] makes it a bridge. Delete its interior. The two local sides can be joined by a small detour around either endpoint through the component complement, because no second endpoint path closes a polygon. They therefore lie in one face, and a boundary traversal encounters $e$ once in each direction.

The null forest and a forest of isolated vertices have connected complement and one face. In a nonempty forest with an edge, a low-degree vertex lemma supplies a leaf and its incident edge.

Delete a leaf and its edge. The remaining drawing is a smaller plane forest. By the induction hypothesis it has one face, and reinserting the pendant edge does not split that face because the edge is a bridge and both its local sides are incident with the same face by [L2].

Repeating the leaf deletion reaches isolated vertices, so every plane forest has one face.

No edge of the common boundary $H$ is a bridge, because [L1] gives a bridge only one incident face. Hence every boundary edge lies on a cycle, and $H$ contains a cycle $C$.

By [L2], $C$ has exactly two complementary regions. Since both $f_1$ and $f_2$ have all of $H$ as boundary, they lie on opposite sides of $C$. Any edge, vertex, chord or attached component of $H$ outside $C$ would lie on only one side of $C$ and could not lie in the frontier of the face on the other side. Thus $H=C$.

If $G$ contained an edge or vertex outside $H=C$, connectedness would attach it through one side of $C$ and alter only that face boundary, contradicting the assumed equality. Therefore $G=C$.

Suppose the facial boundary walk repeats a vertex $v$ before returning to its start. The two portions between consecutive occurrences leave $v$ through different local sectors of the face.

Vertices or edges incident with those two portions lie in different components of $G-v$: a path between them avoiding $v$ would, together with boundary subpaths, cross the face boundary in the plane. Thus $v$ is a cut vertex.

By [L1], two-connectivity supplies two internally vertex-disjoint paths between vertices chosen on the two portions, so deletion of $v$ cannot separate them. This contradicts step 2.1. The boundary walk has no repeated vertex and is therefore a cycle.

A facial boundary $C$ is a cycle by [L1]. It has no chord $xy$: the chord lies on the nonfacial side, and the chord together with each of the two $x$-$y$ arcs of $C$ is a polygon by [L3]. These two polygons bound disjoint subregions of the nonfacial side. Since the facial side contains no graph edge, a path from an internal vertex of one $x$-$y$ arc to an internal vertex of the other, avoiding $x,y$, would have to cross the chord. Thus $\{x,y\}$ would be a vertex cut, contrary to three-connectivity and [L2]. Hence $C$ is induced.

Conversely, let $C$ be induced and suppose $G-V(C)$ is connected or empty. If $C$ is not facial, both complementary regions from [L3] contain graph material. Inducedness rules out a chord as that material, so each side contains a vertex outside $C$. When $G-V(C)$ is connected, a path in it joins vertices on the two sides and must cross $C$, contradicting the plane embedding. If $G-V(C)$ is empty, the drawing consists only of $C$, and both sides are faces. Thus $C$ is facial.

Suppose $G-V(C)$ were disconnected, and let $D_1$ be one of its components. Every component has at least three neighbours on $C$, since one or two such neighbours would be a vertex cut contradicting [L2]. Because $C$ bounds a face, every component lies in the closed complementary side of $C$, which [L3] presents as a region bounded by $C$. Let $a_1,\dots ,a_k$ with $k\ge 3$ be the attachments of $D_1$ in cyclic order on $C$, and let $S$ be a spanning tree of $D_1$ together with one edge to each $a_i$. Then $S$ is connected, lies in that side, and meets $C$ exactly in $\{a_1,\dots ,a_k\}$, so by [L3] the set $S\cup C$ divides the side into exactly $k$ regions, the $i$th bounded by the arc of $C$ from $a_i$ to $a_{i+1}$ carrying no further attachment of $D_1$ together with two paths of $S$. Every other component is connected and meets neither $S$ nor $C$, so each lies inside a single one of those open regions; choose one, say the $i$th, that contains a component, and put $x:=a_i$ and $y:=a_{i+1}$. This is where the alternation of attachments is not enough: two components may share all three of their attachments, in which case no four attachments alternate, and the region argument rather than the crossing argument is what confines them. Let $U$ consist of the open arc of $C$ strictly between $x$ and $y$ together with every component lying in the $i$th region. Distinct components of $G-V(C)$ are non-adjacent, and each component in that region has all of its neighbours on the closed arc from $x$ to $y$, while $D_1$ has no attachment strictly inside that arc. A vertex of the open arc has no neighbour elsewhere on $C$, because step 1.1 has already shown $C$ induced, so $C$ has no chord; and any component adjacent to such a vertex has an attachment strictly inside the arc, hence lies in the $i$th region and is already in $U$. Hence the only neighbours of $U$ outside $U$ are $x$ and $y$, so $\{x,y\}$ is a vertex cut separating $U$ from $D_1$, contradicting [L2]. Thus $G-V(C)$ is connected when nonempty.

Steps 1.1 and 2.1 prove the forward implication, and step 1.2 proves the reverse, including the empty-deletion boundary.

Let $f$ be a face of $G$. By [L2] its boundary walk is a cycle $C$, drawn as a polygon. By [L5] every frontier point of $f$ in the relative interior of an edge puts that whole edge in the frontier, so $\mathrm{Fr}(f)$ is exactly the point set of $C$. Now $f$ is connected and disjoint from $C$, so it lies in one region $R_0$ of $C$ [L1, L4]; $f$ is open, and $\bar{f}\cap R_0=(f\cup C)\cap R_0=f$, so $f$ is also closed in $R_0$. A nonempty clopen subset of the connected $R_0$ is all of it, so the face is one of the two regions of its own boundary cycle.

If instead every face is triangular, the interior of any proposed new plane edge is connected and disjoint from the drawing, so it lies in one face, with both endpoints on that face's boundary [L4]. Those endpoints are already adjacent because that boundary is a triangle, so no missing edge can be added.

The two regions of a polygon $P$ carry different crossing parities. Fix a point $p$ in the relative interior of one of the finitely many segments making up $P$, so $p$ is not a vertex, and by [L6] take a disc $D$ about $p$ small enough to meet $P$ only in that segment. Then $D\setminus P$ is two open half-discs, each connected and disjoint from $P$ and so contained in a single region [L4]; by [L1] there are exactly two regions and each has frontier $P\ni p$, so each meets $D$, and therefore the two half-discs lie in different regions. Only finitely many directions fail to be in general position for $P$ [L3], and only the two directions along the segment fail to meet it transversely, so some direction $d$ avoids both finite sets. Put $q=p-\epsilon d$ and $q^{\mathrm{\prime }}=p+\epsilon d$ with $\epsilon$ small enough that both lie in $D$; since $d$ is not along the segment, $q$ and $q^{\mathrm{\prime }}$ lie in the two different half-discs, and $[q,q^{\mathrm{\prime }}]$ meets $P$ only at $p$. The ray from $q$ in direction $d$ is $[q,q^{\mathrm{\prime }}]$ followed by the ray from $q^{\mathrm{\prime }}$ in direction $d$, so its crossing count is that of the latter plus the single transverse crossing at $p$. Both rays are in general position, so by [L3] those counts are the parities of $q$ and of $q^{\mathrm{\prime }}$, which therefore differ; and parity is constant on each region [L3].

Let $u$ be a vertex of $C$. By [L6] a small enough disc $D$ about $u$ contains no other vertex and meets the drawing only in initial straight segments of the finitely many edges at $u$. Deleting those segments leaves finitely many open sectors of $D$, each connected and disjoint from the drawing and hence inside a single face [L4]. Since $u\in \mathrm{Fr}(f)$, points of $f$ lie in every disc about $u$, so one sector $S$ satisfies $S\subseteq f$, and the straight radius from $u$ into $S$ meets the drawing only at $u$.

Let $u\mathrm{\ne }v$ be vertices of $C$, with radii as in step 2.1 and inner endpoints $u^{\mathrm{\prime }},v^{\mathrm{\prime }}\in f$. By step 1.1 $f$ is a region, hence an open connected plane set and polygonally connected [L4], so a polygonal path joins $u^{\mathrm{\prime }}$ to $v^{\mathrm{\prime }}$ inside $f$; discarding the portion between the first and last visit to each repeated point makes it simple. Concatenating the two radii with it gives a polygonal arc from $u$ to $v$ meeting the drawing only at $u$ and $v$. If $u$ and $v$ are nonadjacent in $G$, drawing the edge $uv$ along that arc keeps the drawing plane, so $G$ is not maximal plane.

Suppose now $G$ is maximal plane and some facial boundary cycle $C$ has length at least four. Let $u_1,u_2,u_3,u_4$ occur in this cyclic order on $C$ and let $P_1,P_2$ be the two $u_1$–$u_3$ subpaths of $C$, with $u_2$ on $P_1$ and $u_4$ on $P_2$. Both pairs are nonconsecutive on $C$, so by step 3.1 $u_1{u}_3$ and $u_2{u}_4$ are edges of $G$, neither an edge of $C$; write $e,e^{\mathrm{\prime }}$ for their arcs. They share no endpoint, so by [L6] the relative interior of each avoids $C$ and the other, and both avoid $f$ because they are part of the drawing. Hence $J_1=e\cup P_1$ and $J_2=e\cup P_2$ are polygons.

From any point off $C\cup e$ there is a ray meeting that finite union of segments transversely in finitely many nonvertex points, by the finiteness count of [L3], and one such ray is in general position for $C$, $e$, $J_1$ and $J_2$ at once. Its crossings with $J_1$ plus its crossings with $J_2$ equal its crossings with $C$ plus twice its crossings with $e$, so those three parities satisfy $J_1+J_2=C$ modulo two at every point off $C\cup e$. Now $f$ avoids $C$, $J_1$ and $J_2$ and is connected, so all three parities are constant on it, say $p_1$, $p_2$ and $p_1+p_2$. The relative interior of $e^{\mathrm{\prime }}$ is connected and also avoids $J_1$ and $J_2$, so its $J_1$- and $J_2$-parities are constant. Its endpoint $u_4$ is off $J_1$ and lies in $\mathrm{Fr}(f)$ by step 1.1, so a neighbourhood of $u_4$ off $J_1$ carrying a constant parity [L3] meets both $f$ and that relative interior, forcing the $J_1$-parity along $e^{\mathrm{\prime }}$ to be $p_1$; symmetrically $u_2\mathrm{\notin }{J}_2$ forces the $J_2$-parity to be $p_2$. The $C$-parity along $e^{\mathrm{\prime }}$ is then $p_1+p_2$, that of $f$. The two regions of $C$ carry different parities by step 1.3, so equal $C$-parity places the relative interior of $e^{\mathrm{\prime }}$ in the same region of $C$ as $f$ — which by step 1.1 is $f$ itself. That is impossible for part of the drawing, so the assumption fails and every facial boundary cycle has length three.

The order assumption excludes the one- and two-vertex degeneracies, and steps 5.1 and 1.2 prove both directions.

Choose a spanning tree $T$ by [L1]. It has all $\mathrm{\mid }V\mathrm{\mid }$ vertices and $\mathrm{\mid }V\mathrm{\mid }-1$ edges, and its plane drawing has one face by the forest proposition. Hence $\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }E(T)\mathrm{\mid }+\mathrm{\mid }F(T)\mathrm{\mid }=\mathrm{\mid }V\mathrm{\mid }-(\mathrm{\mid }V\mathrm{\mid }-1)+1=2$.

Add the edges of $G-E(T)$ in their fixed embedding. Each added edge joins vertices already connected in $T$, so it closes a cycle. By [L2] it splits one old face into two: the edge count and face count each increase by one, while the vertex count is unchanged. Thus the Euler expression remains invariant.

Equivalently, deleting a cycle edge from a connected plane graph merges its two incident faces and decreases both $\mathrm{\mid }E\mathrm{\mid }$ and $\mathrm{\mid }F\mathrm{\mid }$ by one. Deleting a bridge would disconnect the graph and is not used in this connected induction.

Starting from $T$ and adding all remaining edges yields $G$, so the invariant value from step 1.1 is $2$ for $G$.

Insert the connected component drawings one at a time in their inherited positions. Before a component is inserted, its connected drawing lies in one face of the components already inserted. By [L3] choose a spanning tree; [L4] gives it $\mathrm{\mid }V(G_i)\mathrm{\mid }-1$ edges, and [L5] shows that inserting this tree does not split the containing face. Add the remaining edges in their inherited drawing order. Each joins vertices already connected by the tree, hence lies on a cycle, so [L6] shows that its insertion splits one face into two. There are $\mathrm{\mid }E(G_i)\mathrm{\mid }-\mathrm{\mid }V(G_i)\mathrm{\mid }+1=\mathrm{\mid }F(G_i)\mathrm{\mid }-1$ such edges, where the last equality is [L1]. Starting from the one face of the empty drawing therefore gives $\mathrm{\mid }F\mathrm{\mid }=1+{\sum }_i(\mathrm{\mid }F(G_i)\mathrm{\mid }-1)$. Vertices and edges add disjointly by [L2].

Therefore $\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }E\mathrm{\mid }+\mathrm{\mid }F\mathrm{\mid }={\sum }_i(\mathrm{\mid }V(G_i)\mathrm{\mid }-\mathrm{\mid }E(G_i)\mathrm{\mid }+\mathrm{\mid }F(G_i)\mathrm{\mid })-c+1=2c-c+1=1+c$.

For the null graph, $\mathrm{\mid }V\mathrm{\mid }=\mathrm{\mid }E\mathrm{\mid }=c=0$ and $\mathrm{\mid }F\mathrm{\mid }=1$, so the same formula reads $1=1$.

By [L3], $F(G)$ is finite. Count incidences between faces and local edge sides. By [L2] every edge supplies exactly two sides, while the fibre over a face has size equal to its boundary-walk length. Thus [L1] gives ${\sum }_{f\in F}\mathrm{\ell }(f)=2\mathrm{\mid }E\mathrm{\mid }$.

Since each $\mathrm{\ell }(f)\ge g$, summing these inequalities yields $g\mathrm{\mid }F\mathrm{\mid }\le {\sum }_f\mathrm{\ell }(f)=2\mathrm{\mid }E\mathrm{\mid }$.

Suppose for contradiction that $G$ is disconnected. By [L1], choose one connected component $C$ and let $H$ be the plane subgraph formed by all the other components. Both $C$ and $H$ are nonempty.

The point set of the drawing of $C$ is connected: graph paths join its vertices, their polygonal images are connected, and every point of an edge is joined along that edge to an endpoint. This drawing is disjoint from $H$, so it lies in one face $h$ of $H$.

Choose points $p_0$ in the drawing of $C$ and $x$ in the drawing of $H$. On the segment from $p_0$ to $x$, let $x_0$ be the first point in the closed drawing of $H$. The part before $x_0$ lies in the complement of $H$ and is connected to $p_0$, so it lies in $h$ and $x_0$ lies in the frontier of $h$. If $x_0$ lies in an edge interior, [L4] puts the whole edge in that frontier; hence in every case the frontier contains a vertex $y$ of $H$. The drawing of $C$ is a closed finite union of segments disjoint from $y$, so choose a disc $D$ about $y$ that avoids $C$ and meets $H$ only in $y$ and segments incident with $y$. One of the local sectors of $D\setminus H$ lies in $h$; it lies in a face $f$ of $G$, and it approaches $y$, so $y$ belongs to the boundary subgraph of $f$.

Choose a point $q$ in that sector and a point $p$ of the drawing of $C$. The face $h$ is a connected component of the open complement of $H$, so [L3] gives a polygonal path in $h$ from $q$ to $p$. Let $z$ be its first point on the closed drawing of $C$. The part before $z$ avoids every component of $G$ and starts in $f$, so it lies in $f$ and shows that $z$ is in the frontier of $f$. If $z$ is a vertex then the boundary subgraph of $f$ meets $C$ there; if $z$ is in an edge interior, [L4] puts that whole edge, and hence its endpoints in $C$, in the boundary.

The boundary subgraph of $f$ therefore contains a vertex of $C$ and a vertex of $H$. It is disconnected: any path in that boundary subgraph would also be a path in $G$ joining two distinct components, contrary to [L1].

By [F1], however, the boundary subgraph of $f$ is a triangle and is connected. This contradiction is independent of whether $h$ or $f$ is bounded, so it includes the unbounded face; it also uses only that the disconnected graph has two nonempty components, so it covers the smallest permitted order of three. Hence $G$ is connected.

First suppose the graph is connected. If it is a tree then $m=n-1\le 3n-6$. Otherwise simplicity makes every facial boundary walk have length at least three, so [L2] gives $3\mathrm{\mid }F\mathrm{\mid }\le 2m$. Combining this with [L1], $\mathrm{\mid }F\mathrm{\mid }=2-n+m$, yields $3(2-n+m)\le 2m$, hence $m\le 3n-6$.

[L2] supplies more than its inequality: for a connected plane graph it gives the exact facial total ${\sum }_{f\in F}\mathrm{\ell }(f)=2m$, from which that inequality is only the consequence drawn there.

If the graph is disconnected, first redraw it. Each component drawing is a finite union of segments and so is bounded, so translating and scaling the components into pairwise disjoint discs gives a plane drawing of the same abstract graph in which every component meets the unbounded face; the bound to be proved does not depend on the drawing. Now join the components by noncrossing edges through that face until the drawing is connected. This preserves simplicity and planarity, keeps $n$ fixed, and only increases the number of edges. Step 1.1 applied to the augmented graph therefore bounds the original $m$ by $3n-6$.

Let the graph be a plane triangulation with $n\ge 3$ vertices. By [L3] it is connected, and every face has boundary a triangle, so $\mathrm{\ell }(f)=3$ for every face. Then step 1.2 reads $3\mathrm{\mid }F\mathrm{\mid }=2m$, and [L1] gives $\mathrm{\mid }F\mathrm{\mid }=2-n+m$, so $3(2-n+m)=2m$ and $m=3n-6$.

Suppose first the graph is connected. If it is a tree, $m=n-1\le 2n-4$. Otherwise every facial boundary walk has length at least four: lengths one and two are excluded by simplicity except for a lone bridge component, and length three would be a triangle.

In the non-tree case, [L2] with $g=4$ and [L1] give $4(2-n+m)\le 2m$, hence $m\le 2n-4$. Together with the tree case this proves the connected bound.

For a disconnected graph, first redraw it: each component drawing is bounded, so translating and scaling the components into pairwise disjoint discs puts every component on the unbounded face without changing the abstract graph, on which the bound depends. Now join the components through that face by noncrossing bridge edges. No cycle, and hence no triangle, is added; the connected augmented graph has the same $n$ and at least as many edges. Step 2.1 gives the required bound for the original graph.

For $n=1$ or $n=2$, some vertex has degree at most one, hence at most five. Assume $n\ge 3$.

Suppose every vertex had degree at least six. Then [L2] gives $2m\ge 6n$, so $m\ge 3n$, while [L1] gives $m\le 3n-6$. This contradiction proves that some degree is at most five.

By [L1], $K_5$ has $\left(\genfrac{}{}{0px}{}{5}{2}\right)=10$ edges, but [L2] would permit at most $3\cdot 5-6=9$ in a planar graph. Hence $K_5$ is nonplanar.

The graph $K_{3,3}$ has six vertices and nine edges. It is triangle-free because a closed walk alternates between its two parts and therefore has even length. A planar embedding would contradict [L3], whose bound is $2\cdot 6-4=8$.

In a plane drawing of a subdivision, suppressing a degree-two subdivision vertex replaces its two incident polygonal edge arcs by their concatenation and preserves a plane drawing. Repeating this suppression shows that planarity of a subdivision implies planarity of the original graph.

Suppose $G$ contained a subdivision of $K_5$ or $K_{3,3}$. A subgraph of a planar graph inherits a plane drawing, and step 1.1 would turn that drawing into a plane drawing of the corresponding original graph, contradicting [L1].

Let $G$ be two-connected and maximally planar. Every plane embedding of $G$ is maximal plane: otherwise an edge added in that embedding would give a larger planar abstract graph. That embedding is a two-connected plane graph, because two-connectivity is a property of the abstract graph, so [L2] makes it a triangulation and [L1] gives $\mathrm{\mid }E(G)\mathrm{\mid }=3n-6$.

Conversely, if $\mathrm{\mid }E(G)\mathrm{\mid }=3n-6$ and a missing edge could be added planarly, the resulting simple planar graph on the same $n$ vertices would have $3n-5$ edges, contradicting [L1]. Thus $G$ is maximally planar.

Step 2.1 holds for every $n\ge 3$, and step 1.1 supplies the converse whenever $G$ is two-connected, so the two conditions are equivalent there.