Finite planar graph disk cuts and Euler count

A regular edge has a well-defined nonzero tangent ray at each endpoint. On a sufficiently short initial interval its radial distance from that endpoint is strictly increasing: the derivative of squared radial distance is $2t\mathrm{\mid }{\gamma }^{\mathrm{\prime }}(0){\mathrm{\mid }}^2+o(t)>0$. Its image lies in an arbitrarily narrow cone about that ray. Finiteness and distinct incident rays therefore give a small vertex disk in which each incident edge is one radial germ and every sector between consecutive germs contains a smaller straight wedge. At an interior point of an edge a regular local parametrization gives the usual two sides. These assertions persist when a new edge starts strictly inside an existing free wedge.

Subdivide $S$ so that it is a cycle with at least three vertices. For each pair of parallel edges subdivide all but one at a distinct regular interior point. The resulting graph is simple; each subdivision changes $(V,E)$ by $(1,1)$, introduces two opposite rays at its new vertex, and creates no zero sector between distinct incident edge germs. The positive free sectors needed below are the sectors on either side of that subdivided edge. Existing incident rays at old vertices are unchanged.

Polygonal crosscut fact. If a connected open face $f$ has distinct boundary vertices $u,w$ and selected free sectors there, choose short straight segments from each endpoint strictly inside its sector. Their inner endpoints lie in $f$. Join them by a polygonal path in $f$ using [F1], perturbing finitely many collinear overlaps if needed. The finite planar union of this path and the two initial segments contains a simple path from $u$ to $w$; choosing the first departure at $u$ and last arrival at $w$ retains short straight subsegments in the prescribed sectors. Equivalently, erase loops and shorten the endpoint segments at their finitely many intersections with the middle path. This gives a simple polygonal arc with interior in $f$, and with strictly positive sectors on either side at both endpoints.

Connect components. Start with the component containing $S$. If another compact component exists, a shortest segment between this component and the union of the other components gives, after stopping at its first encountered component, an open segment in a common face with endpoints on different components. At an endpoint interior to a regular edge, subdivision makes it a vertex and the shortest segment is normal to that edge; at an old vertex it enters a free sector after an arbitrarily small generic perturbation in that face. Apply step 2.2 in those sectors, so the joined graph retains the local positive-sector property. Each addition reduces the component count, hence finitely many give a connected graph.

Remove cut vertices. Let $v$ be a cut vertex of the connected simple graph, and let $C_1,\dots ,C_k$ be the components of $\mathrm{\Gamma }-v$. Around $v$ some consecutive incident germs belong to different $C_i$; their other endpoints $u,w$ lie on the boundary of the face occupying that sector and are not adjacent (an edge $uw$ would connect the two components without $v$). Step 2.2 joins $u,w$ inside that face without crossing the graph. For the fixed finite vertex set define $\mathrm{\Phi }={\sum }_x(c(\mathrm{\Gamma }-x)-1{)}_{+}$, where $c$ counts connected components. Adding this edge strictly decreases the summand for $x=v$ and cannot increase any summand, since deleting any fixed vertex from the augmented graph only adds an edge or changes nothing. Thus $\mathrm{\Phi }$ decreases. The construction introduces no vertex and keeps the graph simple, so after finitely many additions $\mathrm{\Phi }=0$: the graph has at least three vertices, is connected, and has no cut vertex.

Apply the rooted ear decomposition of [F3] to the 2-connected simple graph of step 3.2, starting with the boundary cycle $S$. We prove by induction that every face inside $S$ has a Jordan graph cycle as its exact frontier and that $V-E+F_{\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{e}}=2$. The initial drawing $S$ has one bounded face and one exterior face by [F2], and $V=E$. Suppose the invariant holds for a partial drawing $H$, and add its next ear $P$, a finite chain of simple graph edges with distinct old endpoints $u,v$, with all internal vertices new and its relative interior disjoint from $H$. As every edge lies in $D$, the connected relative interior of $P$ lies in one bounded face $f$ of $H$. Its frontier is a graph cycle $J$ by induction, and $f$ is the bounded component of ${\mathbb{R}}^2\setminus J$: otherwise a polygonal path inside that component from $f$ to an omitted point would first leave $f$ through its frontier $J$, a contradiction. Let $J_1,J_2$ be the two $u$--$v$ arcs of $J$. Each $J_i\cup P$ is a Jordan curve, even though $P$ need not be polygonal. The region-label proof of the crosscut claim in [F2]'s ear supplier applies verbatim except for its local-two-side sentence: at any $x\in P\setminus \{u,v\}$ choose a neighbourhood disjoint from $J$; the Schönflies plane homeomorphism of the Jordan curve $J_1\cup P$ in [F2] gives a smaller neighbourhood in which the common arc $P$ has exactly two connected local sides. Thus the two new Jordan curves label opposite sides of every interior point of $P$, and the same component/frontier argument splits $f\setminus P$ into exactly two bounded faces whose exact frontiers are $J_1\cup P$ and $J_2\cup P$. Every other face stays unchanged. If the ear has $k$ edges, it adds $k-1$ vertices, $k$ edges and one face, preserving $V-E+F_{\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{e}}=2$. Induction covers the complete drawing. In particular each $f\subset \mathrm{Int}D$ is a Jordan disk by [F2], and its cycle vertices have positive occupied sectors by step 1.1.

Fix one such face with boundary cycle $v_1{v}_2\cdots v_n$, $n\ge 3$. Apply step 2.2 inside it from $v_1$ to $v_2$, using strict interior rays, and select an interior point $p$ on one straight segment of that crosscut. Subdivide the crosscut at $p$. By [F2], it cuts off the Jordan triangle with vertices $(p,v_1,v_2)$ and old boundary edge $v_1{v}_2$; its other Jordan face contains $v_3,\dots ,v_n$. Choose $p$ in the straight part so the remaining face has a positive sector at $p$.

In the remaining face add, successively for $j=3,\dots ,n$, a polygonal crosscut from $p$ to $v_j$ with endpoint rays strictly inside its positive sectors. The crosscut splitting fact [F2] gives at stage $j$ one Jordan triangle $(p,v_{j-1},v_j)$ and one remaining Jordan disk containing the not-yet-used vertices. The final remainder is $(p,v_n,v_1)$. All faces are triangular Jordan disks and each has exactly one edge inherited from the boundary of the old face. Repeating this finite construction in each old face yields only finitely many new edges and vertices.

The new triangles within one old face form a fan: distinct closed triangles meet in one whole spoke, the hub $p$, a common boundary vertex, or not at all. Across different old faces, a new triangle contains only one old boundary edge, so two such triangles can share at most that whole edge or a vertex. Regular graph edges have disjoint relative interiors, and added arcs are interior to their selected faces; thus no other intersection is possible. This proves the stated face-to-face property.

The connected graph before the fan has $V-E+F_{\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{e}}=2$ by the induction of step 4.1. Its exterior face is the unique component outside $S$. A boundary or interior edge subdivision adds one vertex and one edge; a crosscut between existing boundary vertices adds one edge and one bounded face. The hub subdivision and every fan split therefore preserve $V-E+F$ for faces inside $D$. Consequently the final counts satisfy $V-E+F=1$. All original edges persist up to subdivision and every added edge is polygonal, establishing (i)–(iv). The exact AC use is through the arbitrary-Jordan-curve suppliers in [F2]; finite choices and the rooted ear selection of [F3] need no AC.