Finite plane graph ear and face facts

Among the finitely many acyclic subsets of $E(G)$ choose one maximal by inclusion and call it $S$. If the subgraph $(V(G),S)$ had two components, then a path in the connected graph $G$ between vertices in different components would contain an edge whose endpoints lie in different components of $(V(G),S)$; adding that edge to $S$ keeps it acyclic, contradicting maximality. So $(V(G),S)$ is acyclic, connected and spans $V(G)$: it is a spanning tree. The selection is from one nonempty finite collection.

Let $G$ be $2$-connected, so $\mathrm{\mid }V(G)\mathrm{\mid }\ge 3$ by [L2], and let $C$ be a specified cycle of $G$. Such a cycle exists: an acyclic connected graph is a tree, a tree with at least three vertices has a vertex of degree at least two, and such a vertex is a cut vertex, contradicting [L2]. Start with $H=C$ and repeat: if $V(H)\mathrm{\ne }V(G)$, take a component $K$ of $G-V(H)$. It has a neighbour in $V(H)$ because $G$ is connected, and it has at least two distinct attachment vertices, because a unique attachment vertex would be a cut vertex, again contradicting [L2]. Pick distinct attachments $a_1,a_2$ with neighbours $w_1,w_2\in K$, take a simple path in $K$ from $w_1$ to $w_2$ (a single vertex when $w_1=w_2$), and add the ear $a_1{w}_1\cdots w_2{a}_2$, all of whose internal vertices lie in $K$ and are therefore new. If instead $V(H)=V(G)$ but $E(H)\mathrm{\ne }E(G)$, add one missing edge as a one-edge ear. Each step adds at least one edge of $G$ and removes none, so after at most $\mathrm{\mid }E(G)\setminus E(C)\mathrm{\mid }$ steps the process stops at a subgraph with $V(H)=V(G)$ and $E(H)=E(G)$, that is, at $G$. Adding a path with distinct endpoints to a $2$-connected graph preserves $2$-connectivity: after deleting any one vertex, the old graph $H$ is unchanged when the deleted vertex is new and remains connected when it lies in $H$ by 2-connectivity, and every remaining part of the added path is attached to a surviving endpoint of that path, so the result is connected and still has at least three vertices.

Crosscut claim. Let $J$ be a Jordan curve with complementary regions $U$ (bounded) and $O$ (unbounded), let $p\mathrm{\ne }q$ be points of $J$, and let $P$ be a simple polygonal arc from $p$ to $q$ whose remaining points all lie in one region $V$ of ${\mathbb{R}}^2\setminus J$; write $W$ for the region of ${\mathbb{R}}^2\setminus J$ different from $V$. Let $J_1,J_2$ be the two closed arcs of $J$ from $p$ to $q$ and put $D_i=J_i\cup P$. First, each $D_i$ is a Jordan curve: pasting parametrizations of $J_i$ and $P$ at their common endpoints gives a continuous bijection from the unit circle onto $D_i$, which is a homeomorphism because the unit circle is compact metric and $D_i$ carries the subspace topology and restricted metric of the plane; hence $D_i$ is compact and closed in the plane. [L7, L8] By [F1] if $J$ is a polygon, and otherwise by [A1, F2], each $D_i$ has exactly two complementary regions, and each of them has frontier $D_i$. Let $Z_i$ be the region of ${\mathbb{R}}^2\setminus D_i$ containing $W$, which is well defined because $W$ is connected and disjoint from $D_i$, and let $Y_i$ be the other region. Every point of $J\setminus J_i$ lies in $Z_i$: such a point $x$ has a ball $B$ about it disjoint from $D_i$, and $B$ meets $W$ because $x$ lies in the frontier of $W$, which is $J$; since $B$ is connected and contained in ${\mathbb{R}}^2\setminus D_i$, it lies in $Z_i$. Consequently $Y_i$ is disjoint from $J$, as it misses $J_i\subseteq D_i$ and misses $J\setminus J_i\subseteq Z_i$; being connected, $Y_i$ lies in one region of ${\mathbb{R}}^2\setminus J$, and since $W\subseteq Z_i$ it is not $W$, so $Y_i\subseteq V$. Next $Y_2\subseteq Z_1$: the set $Y_2$ misses $P\subseteq D_2$ and misses $J$, so it is contained in ${\mathbb{R}}^2\setminus D_1$; and $Y_2$ has points arbitrarily close to each point of the open arc $J_2\setminus \{p,q\}$, because the frontier of $Y_2$ is $D_2$; that arc is contained in $J\setminus J_1\subseteq Z_1$, and $Z_1$ is open, so $Y_2$ meets $Z_1$ and therefore lies in $Z_1$. Symmetrically $Y_1\subseteq Z_2$, so $Y_1\cap Y_2=\mathrm{\varnothing }$. Now fix $x\in P\setminus \{p,q\}$. Because $P$ is a finite simple polygonal arc, choose a sufficiently small ball $B\subseteq V$ about $x$ that misses every nonlocal segment of $P$; then $B\cap P$ is just the one segment germ through $x$, or the two adjacent germs when $x$ is a polygonal vertex. Since $V$ misses $J$, we have $B\cap D_i=B\cap P$, so $B\setminus D_i=B\setminus P$ has exactly two connected local sides: two half-disks in the straight case and two sectors at a bend. Each local side is connected and contained in ${\mathbb{R}}^2\setminus D_i$, so it lies in $Z_i$ or in $Y_i$; as $x$ lies in the frontier of both $Z_i$ and $Y_i$, the ball $B$ meets both, so the two local sides receive opposite labels for each $i$; and no local side lies in both $Y_1$ and $Y_2$, because those sets are disjoint. Hence one local side lies in $Y_1$ and the other in $Y_2$. Finally let $N$ be a component of $V\setminus P$. It is open in the plane and closed in $V\setminus P$. Its closure in $V$ meets $P\setminus \{p,q\}$: otherwise it would be closed in $V$, and it is also open in $V$, so it would equal the connected set $V$, although the nonempty set $P\setminus \{p,q\}$ lies in $V$ and misses $V\setminus P$. So a ball $B\subseteq V$ about a point of that closure meets $N$, and $N$ misses $P$, so $N$ meets $B\setminus P$ and hence meets $Y_1\cup Y_2$. Since each $Y_i$ is open and has frontier $D_i$, which is disjoint from $V\setminus P$, each $Y_i$ is also closed in $V\setminus P$; the connected set $N$, meeting $Y_1\cup Y_2$, therefore lies in $Y_1$ or in $Y_2$. Hence $V\setminus P=Y_1\bigsqcup Y_2$ is exactly the decomposition into components, while $W$ remains a region of ${\mathbb{R}}^2\setminus (J\cup P)$ with frontier $J$. Therefore ${\mathbb{R}}^2\setminus (J\cup P)$ has exactly three regions, with frontiers $J,D_1,D_2$. The polygonal case of this claim is choice-free, and the arbitrary-Jordan case uses AC exactly through [F2].

Polygonal face induction. Let now $G$ be $2$-connected and polygonally drawn. Build it by the ear decomposition of step 1.2 from any cycle, and induct on the number of added ears, with the invariant: every face of the current drawing has a simple cycle as its facial boundary walk, and the drawing satisfies $V-E+F=2$. For the initial cycle $C_0$, which is a polygon, [F1] gives exactly two regions with frontier $C_0$, so each facial boundary walk traverses the cycle once, and $V-E+F=\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }V\mathrm{\mid }+2=2$. Assume the invariant for a drawing $H$, and let $Q$ be the next ear, a polygonal arc with distinct endpoints $u\mathrm{\ne }v$ on the drawing of $H$ and with relative interior disjoint from that drawing. The relative interior of $Q$ is connected and lies in the complement of the drawing of $H$, so it is contained in a single face $F$; let $J$ be the boundary cycle of $F$ and let $V$ be the region of ${\mathbb{R}}^2\setminus J$ containing $F$. By [L4] the frontier of $F$ meets the drawing $X_H$ of $H$ exactly in $J$. Since a face is a component of the open complement of $X_H$, its frontier lies in $X_H$; hence $\mathrm{Fr}(F)=J$. If $F$ were a proper subset of $V$, [L6] would give a polygonal path in $V$ from a point of $F$ to a point of $V\setminus F$. The first point at which that path leaves the open set $F$ would lie in $\mathrm{Fr}(F)\cap V=J\cap V=\mathrm{\varnothing }$. Thus $F=V$. Apply step 1.3 to the polygonal Jordan curve $J$, the distinct points $u,v\in J$ and the polygonal arc $Q$, whose relative interior lies in $V$: the two arcs $J_1,J_2$ of $J$ from $u$ to $v$ give graph cycles $D_i=J_i\cup Q$ of the new drawing, and $F\setminus Q=Y_1\bigsqcup Y_2$, where $Y_i$ is the region of ${\mathbb{R}}^2\setminus D_i$ that does not contain the region of ${\mathbb{R}}^2\setminus J$ different from $V$, and the frontier of $Y_i$ is $D_i$. Every other face $F^{\mathrm{\prime }}$ of $H$ is disjoint from $Q$, because the relative interior of $Q$ lies in $F$ and the endpoints of $Q$ lie in the drawing of $H$; so $F^{\mathrm{\prime }}$ is a connected subset of the complement of the new drawing, and it is closed there because its frontier lies in the drawing of $H$ and misses the relative interior of $Q$, which lies in the open face $F$. Distinct faces of $H$ remain distinct regions, and every point of the complement of the new drawing belongs either to an old face other than $F$ or to $F\setminus Q=Y_1\cup Y_2$. Hence the regions of the new drawing are exactly the faces of $H$ other than $F$, together with $Y_1$ and $Y_2$; their frontiers are the old boundary cycles together with $D_1$ and $D_2$, so the invariant passes to the new drawing. An ear with $k\ge 1$ edges contributes $k-1$ new vertices, $k$ new edges and one new region, so $V-E+F$ is unchanged. Induction over the finitely many ears proves the facial-cycle and Euler claims for $G$.

Let $G$ be any connected polygonally drawn finite simple graph and let $T$ be a spanning tree of $G$, chosen as in step 1.1. The drawn subgraph $T$ is a polygonally embedded finite forest, so by [L5] it has exactly one face and $\mathrm{\mid }E(T)\mathrm{\mid }=\mathrm{\mid }V(G)\mathrm{\mid }-1$; therefore $V-E+F=2$ for $T$. Delete the edges of $G\setminus T$ one at a time, in any order. At each stage the current drawing $H$ still contains $T$, so it is connected, and the edge $e$ being deleted lies on a cycle of $H$: the unique path in $T$ between its endpoints, together with $e$, is a cycle. By [L4] the relative interior of $e$ lies in the frontier of exactly two distinct faces $F_1\mathrm{\ne }{F}_2$ of $H$, one on each local side, and in the frontier of no other face. Let $X$ be the drawing of $H$, put $\mathrm{\Omega }={\mathbb{R}}^2\setminus (X\setminus \mathrm{int}(e))$, and put $R=F_1\cup \mathrm{int}(e)\cup F_2$, where $\mathrm{int}(e)$ is the relative interior of the polygonal arc $e$. The set $R$ is connected: each connected face $F_i$ has every point of $\mathrm{int}(e)$ in its closure, so adjoining that connected arc joins the two faces. It is open in $\mathrm{\Omega }$: at each point $x\in \mathrm{int}(e)$ a sufficiently small disk misses $X\setminus \mathrm{int}(e)$, and the local polygonal arc of $e$ separates the disk into two sides lying respectively in $F_1$ and $F_2$ by [L4]; thus the whole disk lies in $R$. At points of the faces openness is immediate. The old faces other than $F_1,F_2$ are open subsets of $\mathrm{\Omega }$, and $\mathrm{\Omega }$ is the disjoint union of these faces and $R$. Therefore $R$ is also closed in $\mathrm{\Omega }$, as is each other old face: the complement of each is a union of the displayed open sets. Since all these sets are connected, they are exactly the connected components of $\mathrm{\Omega }$. Thus deleting $e$ merges precisely $F_1,F_2$ and leaves all other faces distinct. Each deletion lowers $E$ and $F$ by one and preserves $V-E+F$, so after the finitely many deletions the expression for $G$ equals that for $T$, namely $2$. This argument also covers the one-vertex graph with no edges, where $F=1$.

Let $G$ be connected, simple, bipartite and polygonally drawn with $V\ge 3$, and fix a bipartition $(A,B)$ as in [L3]. Every face has a facial boundary walk, a closed walk of $G$ that traverses each edge of its frontier once per local side [L4]. A closed walk $(v_0,\dots ,v_{\mathrm{\ell }})$ of a bipartite graph has even length: each step interchanges $A$ and $B$, so $v_i$ lies in $A$ or in $B$ according as $i$ is even or odd, and $v_{\mathrm{\ell }}=v_0$ forces $\mathrm{\ell }$ even. Hence every facial walk has even length. No facial walk has length $1$ or $2$. A walk of length $1$ would traverse a loop, excluded in a simple graph; a facial walk of length $2$ traverses the single edge $e=\{v_0,v_1\}$ twice, and the frontier of that face would then be exactly the point set of $e$. But $V\ge 3$ gives a vertex $y$ off $e$, and ${\mathbb{R}}^2\setminus e$ is polygonally path connected by [L9], so a polygonal path in ${\mathbb{R}}^2\setminus e$ from a point of that face to $y$ would have a first parameter $t_0$ at which it leaves the face, and that point would lie in the frontier of the face, hence in the point set of $e$, contradicting that the path avoids $e$. Hence every facial walk has length at least $4$. Each edge has exactly two local sides and each local side is traversed exactly once by the walk of the face on that side, so the sum of the lengths of all facial walks is $2E$; a bridge borders one face on both local sides [L4] and is traversed twice by that walk. Therefore $4F\le 2E$. With $F=2-V+E$ from step 2.2 this gives $2E-2V+4\le E$, that is $E\le 2V-4$. The graph $K_{3,3}$ is connected and bipartite with $V=6$ and $E=9$ by [L3], and $9>8=2\cdot 6-4$, so $K_{3,3}$ has no polygonal plane drawing.

Hybrid induction. Let now $G$ be $2$-connected, so $\mathrm{\mid }V(G)\mathrm{\mid }\ge 3$ by [L2], and drawn as in the hybrid hypothesis: the cycle $C$ is drawn as a Jordan curve, and every other edge arc has its relative interior in the bounded region $U$ of ${\mathbb{R}}^2\setminus C$. Build $G$ by the ear decomposition of step 1.2 from the specified cycle $C$, and induct on the number of added ears, with the invariant: the exterior region of $C$ is a face with boundary cycle $C$, and every other face has a Jordan curve as frontier, that frontier being a graph cycle of the current drawing. For the initial drawing $C$, [F2] gives exactly two regions, the bounded $U$ and the exterior, each with frontier $C$, so both facial boundaries are the cycle $C$, and $V-E+F=\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }V\mathrm{\mid }+2=2$. Let the next ear $Q$ with $k\ge 1$ edges be added, with distinct endpoints $u\mathrm{\ne }v$ on the drawing of $H$ and relative interior disjoint from it; by hypothesis that relative interior lies in $U$. It is connected, so it lies in a single face $F$ of $H$, and $F$ is not the exterior region, which is disjoint from $U$. Hence $F$ is a bounded face with a Jordan graph cycle $J$ as its frontier. Let $V$ be the region of ${\mathbb{R}}^2\setminus J$ containing $F$. If $F$ were a proper subset of $V$, [L6] would give a polygonal path in $V$ from a point of $F$ to a point of $V\setminus F$. The first point at which it leaves $F$ would lie in $\mathrm{Fr}(F)\cap V=J\cap V=\mathrm{\varnothing }$. Thus $F=V$, and $V$ is the bounded region because $F\subseteq U$. In this AC-qualified hybrid argument, invoke [F2] for Jordan separation in the crosscut proof of step 1.3 even when $J$ happens to be polygonal; the optional [F1] choice-free branch of that earlier proof is not used here. Apply the bounded case of step 1.3 to $J$, $u,v$ and the polygonal arc $Q$: the curves $D_i=J_i\cup Q$ are Jordan curves and graph cycles of the new drawing, $F\setminus Q=Y_1\bigsqcup Y_2$, and the frontier of $Y_i$ is $D_i$. Every old face $F^{\mathrm{\prime }}\mathrm{\ne }F$ misses the relative interior of $Q$, so it remains connected and open in the complement of the new drawing. Its old frontier is a Jordan graph cycle contained in the old graph and hence in the new graph, so $F^{\mathrm{\prime }}$ is also closed in that new complement. It therefore remains one component with the same frontier; the exterior region of $C$ is among these unchanged faces. Hence the invariant passes to the new drawing, and an ear with $k$ edges contributes $k-1$ vertices, $k$ edges and one region, so $V-E+F$ is unchanged. Induction over the finitely many ears proves both hybrid conclusions. All selections here are finite, and AC enters only through [F2], used for every Jordan crosscut in this hybrid argument.