# Sphere maps

*Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).*

Barnette's conjecture asserts that every cubic, bipartite, planar, \(3\)-connected graph has a Hamiltonian cycle. It was recorded by Grünbaum in the 1969 Waterloo proceedings and belongs to the line of questions opened by Tait's conjecture for cubic polyhedral graphs, which Tutte disproved; Alt, Payne, Schmidt and Wood, and Gorsky, Steiner and Wiederrecht, discuss its history and many equivalent forms [APSW, GSW]. Goodey proved it when every face has four or six sides; Feder and Subi allowed faces of any length in one class of a proper \(3\)-colouring of the faces, with only quadrilaterals and hexagons in the other two [FS]; Kardoš proved the related Barnette–Goodey conjecture for cubic polyhedral graphs with faces of length at most six [Kar]; and Schnieders proved the case of faces of length at most eight [Sch]. This course presents OpenAI's proof of the full conjecture [OpenAI-B]:

**Theorem** (OpenAI 2026; Theorem 6.1 of [Two induced trees and a Hamiltonian cycle](two-induced-trees-and-a-hamiltonian-cycle.md)). Every finite simple graph that is cubic, bipartite and \(3\)-connected and carries a sphere map has a Hamiltonian cycle.

A *sphere map* is a combinatorial description of a drawing on the sphere, introduced in Section 1. By the classical embedding theorem, every plane embedding of a connected graph gives a sphere map, so the theorem includes Barnette's conjecture; that bridge from topology is stated in Section 5 and is the one result of the course recorded as an open obligation. The proof works with the dual triangulation: a Hamiltonian cycle of the cubic graph corresponds to a partition of the vertices of the triangulation into two sets that each induce a tree. This first lesson develops the facts about sphere maps that the later lessons use: faces and the Euler characteristic, deletion of edges, duality, the two sides of a cycle, an Euler count for one side, and the faces of a connected submap. Everything is proved by counting and linear algebra over the field with two elements. The later lessons are [Triangulations from cubic bipartite graphs](triangulations-from-cubic-bipartite-graphs.md), [Pairs of states](pairs-of-states.md), [A cancelling sum over pairs](a-cancelling-sum-over-pairs.md) and [Two induced trees and a Hamiltonian cycle](two-induced-trees-and-a-hamiltonian-cycle.md). The course [Van Kampen diagrams](course:van-kampen-diagrams/plane-maps) builds plane maps and van Kampen's lemma of combinatorial group theory on the results of this lesson.

## 1. Maps, faces and the Euler characteristic

**Definition 1.1.** A *map* \(M\) consists of a finite nonempty set \(\Delta\) of *darts*, an involution \(\theta\) of \(\Delta\) without fixed points, and a permutation \(\sigma\) of \(\Delta\), such that the group generated by \(\sigma\) and \(\theta\) acts transitively on \(\Delta\). Its *vertices* are the orbits of \(\sigma\), its *edges* are the orbits \(\{d,\theta d\}\) of \(\theta\), and its *faces* are the orbits of
\[
\varphi=\sigma\theta .
\]
The dart \(d\) *leaves* the vertex containing it, its *tail*, and *enters* the tail of \(\theta d\), its *head*. The cyclic order of the darts in a vertex is its *rotation*. The face containing \(d\) is called the face *on the left of* \(d\) and written \(\operatorname{face}(d)\); its *length* is the number of its darts. The *trivial map* has one vertex, no darts and, by convention, one face.

The underlying graph of \(M\) has the vertices and edges of \(M\), the edge \(\{d,\theta d\}\) joining the tails of \(d\) and \(\theta d\). It is a connected multigraph, possibly with loops (an edge whose two darts leave the same vertex) and parallel edges. Conversely, a *rotation system* on a connected multigraph, that is, a cyclic order of the darts leaving each vertex, defines a map. The *Euler characteristic* of a map is \(\chi(M)=V-E+F\), the numbers of vertices, edges and faces, and \(M\) is a **sphere map** if \(\chi(M)=2\). A map with several components (in the sense of its underlying graph) is treated component by component; an isolated vertex is a trivial map.

**Lemma 1.2.** For every dart \(d\), the dart \(\varphi(d)\) leaves the head of \(d\). Hence the darts of a face, in the order \(d,\varphi(d),\varphi^2(d),\dots\), form a closed walk.

*Proof.* \(\theta d\) leaves the head of \(d\), and \(\sigma\) preserves vertices. \(\square\)

**Example 1.3.** (a) A single edge \(\{d,d'\}\) between two vertices, each with one dart: \(\sigma\) fixes both darts, \(\varphi(d)=\sigma(d')=d'\) and \(\varphi(d')=d\). There is one face, and \(\chi=2-1+1=2\).

(b) A single loop \(\{d,d'\}\) at one vertex with rotation \((d\ d')\): \(\varphi(d)=\sigma(d')=d\) and \(\varphi(d')=d'\). There are two faces, and \(\chi=1-1+2=2\).

(c) For the complete graph on \(\{1,2,3,4\}\) with the rotations \((12,13,14)\), \((21,24,23)\), \((31,32,34)\), \((41,43,42)\) at the four vertices, where \(xy\) is the dart from \(x\) to \(y\), one finds the four faces \((12,24,41)\), \((13,32,21)\), \((14,43,31)\), \((23,34,42)\), so \(\chi=4-6+4=2\). With the rotation \((21,23,24)\) at vertex \(2\) instead, one finds two faces and \(\chi=0\).

**Deletion.** For an edge \(e=\{d,d'\}\) of \(M\), the map \(M-e\) has darts \(\Delta'=\Delta\setminus\{d,d'\}\), the restriction of \(\theta\), and the rotation \(\sigma'\) that skips the deleted darts: \(\sigma'(x)=\sigma^j(x)\) for the least \(j\ge1\) with \(\sigma^j(x)\notin\{d,d'\}\). Its vertices are those of \(M\); a vertex whose only darts were \(d\) or \(d'\) becomes isolated. Write \(\varphi'=\sigma'\theta\).

**Lemma 1.4** (Deleting an edge). Faces of \(M\) containing neither \(d\) nor \(d'\) are faces of \(M-e\).

(a) If \(d\) and \(d'\) lie in different faces \((d,a_1,\dots,a_p)\) and \((d',b_1,\dots,b_q)\), written in the order of \(\varphi\), then \(a_1,\dots,a_p,b_1,\dots,b_q\), in this cyclic order, form one face of \(M-e\) (if \(p+q\ge1\); if \(p=q=0\), the map is a single loop and \(M-e\) is the trivial map, with its one face).

(b) If they lie in one face \((d,a_1,\dots,a_p,d',b_1,\dots,b_q)\), then \((a_1,\dots,a_p)\) and \((b_1,\dots,b_q)\) are faces of \(M-e\), each if it is nonempty.

*Proof.* For \(x\in\Delta'\), \(\varphi'(x)=\sigma'(\theta x)\) equals \(\varphi(x)\) unless \(\varphi(x)=\sigma(\theta x)\in\{d,d'\}\). Note that \(\sigma(d)=\varphi(d')\) and \(\sigma(d')=\varphi(d)\).

(a) The darts with \(\varphi(x)\in\{d,d'\}\) are \(a_p\) (when \(p\ge1\)) and \(b_q\) (when \(q\ge1\)). For \(x=a_p\) we have \(\sigma(\theta a_p)=d\), so \(\varphi'(a_p)=\sigma(d)=\varphi(d')=b_1\) if \(q\ge1\); if \(q=0\), then \(\sigma(d)=\varphi(d')=d'\) is skipped and \(\varphi'(a_p)=\sigma(d')=\varphi(d)=a_1\). Symmetrically \(\varphi'(b_q)=a_1\) if \(p\ge1\) and \(b_1\) if \(p=0\).

(b) Here \(\varphi(a_p)=d'\) and \(\varphi(b_q)=d\). For \(x=a_p\), \(\sigma(\theta a_p)=d'\) and \(\sigma(d')=\varphi(d)=a_1\ne d\), so \(\varphi'(a_p)=a_1\). Likewise \(\varphi'(b_q)=\sigma(d)=\varphi(d')=b_1\). \(\square\)

**Lemma 1.5.** If the underlying graph of a map is a tree with at least one edge, the map has exactly one face.

*Proof.* By induction on the number of edges; Example 1.3(a) is the case of one edge. Otherwise choose a leaf \(v\) with its only dart \(d'\), and let \(d=\theta d'\) leave the neighbour \(u\). Then \(\varphi(d)=\sigma(d')=d'\), so \(d\) and \(d'\) lie in one face \((d,d',b_1,\dots,b_q)\). If \(q=0\), then \(\varphi(d')=\sigma(d)=d\), so \(u\) is a leaf as well and the tree has one edge. Hence \(q\ge1\). By Lemma 1.4(b), deleting the edge (and the isolated vertex \(v\)) leaves the face \((b_1,\dots,b_q)\) and all other faces unchanged. By induction the smaller tree has one face, so \(M\) has one face as well. \(\square\)

An edge is a *bridge* if deleting it disconnects the underlying graph.

**Proposition 1.6.** (a) Every map has \(\chi\le2\).

(b) In every map, the two darts of a bridge lie in the same face.

(c) In a sphere map, the two darts of an edge \(e\) that is not a bridge lie in different faces, and \(M-e\) is a sphere map in which these two faces have merged as in Lemma 1.4(a).

(d) If \(e\) is a bridge of a sphere map \(M\), both components of \(M-e\) are sphere maps.

(e) Deleting any set of edges from a sphere map leaves a map each of whose components (including isolated vertices) is a sphere map.

*Proof.* (b) The face of the dart \(d\) of a bridge, from \(u\) to \(v\), is a closed walk through \(d\) (Lemma 1.2). A closed walk that crosses a bridge from \(u\) to \(v\) must cross it back, so it contains \(d'=\theta d\); a face contains each dart at most once.

(a) By induction on the number \(E\) of edges; trivial maps have \(\chi=2\). If every edge is a bridge, the underlying graph is a tree (a loop or a parallel edge is never a bridge), and Lemma 1.5 gives \(\chi=V-(V-1)+1=2\). Otherwise let \(e\) be an edge that is not a bridge. Then \(M-e\) is a connected map with \(E-1\) edges, \(\chi(M-e)\le2\) by induction, and by Lemma 1.4 its number of faces \(F'\) satisfies \(F'\ge F-1\). Hence \(\chi(M)=\chi(M-e)-1+(F-F')\), which is at most \(\chi(M-e)\le2\).

(c) With the notation of (a), \(\chi(M)=2\) and \(\chi(M)=\chi(M-e)-1+(F-F')\); since \(F-F'\le1\) and \(\chi(M-e)\le2\), this forces \(F'=F-1\) and \(\chi(M-e)=2\). By Lemma 1.4, \(F'=F-1\) happens in case (a), or in case (b) with \(p=q=0\). In the latter case \(\varphi(d)=d'\) and \(\varphi(d')=d\), so \(\sigma(d')=d'\) and \(\sigma(d)=d\): both ends of \(e\) are leaves and \(M\) is a single edge, in which \(e\) is a bridge. Hence the two darts lie in different faces.

(d) By (b) we are in case (b) of Lemma 1.4. The walk \(a_1,\dots,a_p\) runs from \(v\) back to \(v\) in the component of \(v\), and \(b_1,\dots,b_q\) in the component of \(u\); an empty piece corresponds to an isolated vertex, which carries one face by convention. So the components \(M_1\), \(M_2\) together have \(F+1\) faces, and
\[
\begin{aligned}
&\chi(M_1)+\chi(M_2)\\
&\quad=V-(E-1)+(F+1)\\
&\quad=\chi(M)+2=4 .
\end{aligned}
\]
As each is at most \(2\) by (a), both equal \(2\).

(e) Delete the edges one at a time and apply (c) and (d) to the component containing the deleted edge. \(\square\)

## 2. Duality

**Lemma 2.1.** For a map \(M=(\Delta,\theta,\sigma)\), the triple \(M^*=(\Delta,\theta,\sigma\theta)\) is a map, the *dual* of \(M\). The vertices of \(M^*\) are the faces of \(M\), its faces are the vertices of \(M\), its edges are those of \(M\), and \((M^*)^*=M\). In particular \(\chi(M^*)=\chi(M)\), and the dual of a sphere map is a sphere map. The dual edge \(e^*\) of \(e=\{d,\theta d\}\) joins \(\operatorname{face}(d)\) and \(\operatorname{face}(\theta d)\); it is a loop exactly when \(e\) has the same face on both sides.

*Proof.* The group generated by \(\sigma\theta\) and \(\theta\) equals the group generated by \(\sigma\) and \(\theta\). The face permutation of \(M^*\) is \((\sigma\theta)\theta=\sigma\), and the rotation of \((M^*)^*\) is \((\sigma\theta)\theta=\sigma\). \(\square\)

**Lemma 2.2** (Trees and cotrees). Let \(M\) be a sphere map and \(S\) a set of edges forming a spanning tree of its underlying graph. Then the dual edges of the edges outside \(S\) form a spanning tree of the underlying graph of \(M^*\). If \(S\) is only a spanning forest, these dual edges form a connected spanning subgraph of \(M^*\).

*Proof.* Delete the edges outside \(S\) one at a time. Throughout, the current map contains the spanning tree \(S\), so it is connected and each deleted edge is not a bridge of the current map. By induction, every current face consists of the remaining darts of a set of original faces, these sets partitioning the original faces: by Proposition 1.6(c) each deletion merges the two current faces containing the darts of the deleted edge \(e\). Hence each deletion joins two different classes, namely those containing \(\operatorname{face}(d)\) and \(\operatorname{face}(\theta d)\) for the original faces, which are the ends of \(e^*\). The dual edges therefore never close a cycle, so they form a forest on the faces of \(M\). At the end the current map is the tree \(S\), which has one face (Lemma 1.5), so all original faces lie in one class and the forest is a spanning tree. If \(S\) is a spanning forest, extend it to a spanning tree \(S'\); the dual edges of the edges outside \(S\) contain the spanning tree belonging to \(S'\). \(\square\)

## 3. The two sides of a cycle

We work over the field \(\mathbb F_2\) with two elements and identify a set of edges with its indicator vector in \(\mathbb F_2^E\). The *cycle space* \(\mathcal Z(G)\) of a multigraph \(G\) consists of the edge sets in which every vertex has even degree, a loop counting twice.

**Lemma 3.1.** (a) If \(G\) is connected, \(\dim\mathcal Z(G)=E-V+1\).

(b) For a face \(f\) of a map, let \(b_f\) be the set of edges having exactly one dart in \(f\). Then \(b_f\in\mathcal Z\).

(c) In a sphere map, the vectors \(b_f\) span \(\mathcal Z\), and the only nonempty set \(\mathcal A\) of faces with \(\sum_{f\in\mathcal A}b_f=0\) is the set of all faces.

*Proof.* (a) The map \(\partial:\mathbb F_2^E\to\mathbb F_2^V\) sending a non-loop edge to the sum of its two ends and a loop to \(0\) has kernel \(\mathcal Z(G)\). Its image consists of vertex sets of even size: every \(\partial e\) has even size, and a path from \(u\) to \(v\) has image \(\{u,v\}\). So the image has dimension \(V-1\), and rank–nullity gives (a).

(b) The face is a closed walk (Lemma 1.2), whose edges, counted with multiplicity, have even degree at every vertex. Reducing modulo \(2\) removes the edges traversed twice.

(c) Every edge has its two darts in one face, contributing to no \(b_f\), or in two faces, contributing to both. So \(\sum_{\text{all }f}b_f=0\), and \(\sum_{f\in\mathcal A}b_f=0\) means that every edge with darts in two different faces has both or neither of them in \(\mathcal A\). These pairs of faces are the ends of the non-loop edges of \(M^*\), which is connected, so \(\mathcal A\) is empty or all faces. Hence the \(b_f\) span a space of dimension \(F-1=E-V+1=\dim\mathcal Z\), using \(\chi=2\) and (a). \(\square\)

A *cycle* in a map is a connected subgraph in which every vertex has degree \(2\); its *length* is its number of edges, which equals its number of vertices. Loops are cycles of length \(1\), and two parallel edges form a cycle of length \(2\).

**Theorem 3.2** (Two sides of a cycle). Let \(C\) be a cycle in a sphere map \(M\). There is a partition of the faces of \(M\) into two nonempty sets \(\mathcal A,\mathcal A'\), unique up to exchanging them, such that an edge lies in \(C\) exactly when its two darts lie in faces on different sides. We call \(\mathcal A\) and \(\mathcal A'\) the *sides* of \(C\).

*Proof.* \(C\in\mathcal Z\), so by Lemma 3.1(c) \(C=\sum_{f\in\mathcal A}b_f\) for a set \(\mathcal A\) determined up to complement. An edge with both darts in one face contributes to no \(b_f\); an edge with darts in faces \(f_1\ne f_2\) appears in the sum exactly when one of \(f_1,f_2\) lies in \(\mathcal A\). Both sides are nonempty because \(C\ne\varnothing\). \(\square\)

**Lemma 3.3** (Orientation). Orient the cycle \(C\), that is, choose for each of its edges the dart that follows the cyclic direction. The faces on the left of these darts all lie on one side of \(C\), and the opposite orientation gives the other side.

*Proof.* For a loop there is one dart. Otherwise let \(d\) enter a vertex \(v\) and let \(d_2\) be the next dart of the orientation, leaving \(v\). Going around \(v\) from \(\theta d\) in the direction of \(\sigma\), let \(x_1=\sigma(\theta d),\dots,x_j\) be the darts before \(d_2\); they belong to edges outside \(C\), because \(v\) has degree \(2\) in \(C\). The face \(\operatorname{face}(d)\) contains \(\varphi(d)=x_1\) (or \(d_2\) if \(j=0\)), and for each \(i\), \(\operatorname{face}(x_i)\) and \(\operatorname{face}(\theta x_i)\) lie on the same side because the edge of \(x_i\) is not in \(C\), while \(\operatorname{face}(\theta x_i)\) contains \(\varphi(\theta x_i)=\sigma(x_i)\), the next dart. Hence \(\operatorname{face}(d)\) and \(\operatorname{face}(d_2)\) lie on the same side. Reversing the orientation replaces each dart \(d\) by \(\theta d\), whose face lies on the other side because the edge belongs to \(C\). \(\square\)

A vertex not on \(C\) is *strictly inside* the side \(\mathcal A\) if the faces on the left of all darts leaving it lie in \(\mathcal A\).

**Lemma 3.4.** (a) Every vertex not on \(C\) is strictly inside exactly one side.

(b) If a vertex \(x\) is strictly inside \(\mathcal A\), every edge at \(x\) has both darts in faces of \(\mathcal A\), and its other end lies on \(C\) or strictly inside \(\mathcal A\).

*Proof.* (a) For darts \(x\), \(\sigma(x)\) at such a vertex, \(\operatorname{face}(\theta x)\) contains \(\varphi(\theta x)=\sigma(x)\), and \(\operatorname{face}(x)\), \(\operatorname{face}(\theta x)\) lie on one side because the edge of \(x\) is not in \(C\). Going around the vertex, all these faces lie on one side.

(b) For a dart \(d\) leaving \(x\), \(\operatorname{face}(d)\in\mathcal A\), and \(\operatorname{face}(\theta d)\) contains \(\varphi(\theta d)=\sigma(d)\), which leaves \(x\), so it lies in \(\mathcal A\) as well. If the other end \(y\) is not on \(C\), it is strictly inside one side by (a), and the face of \(\theta d\), which leaves \(y\), shows that this side is \(\mathcal A\). \(\square\)

**Proposition 3.5** (Euler count for a side). Let \(C\) be a cycle of length \(h\) in a sphere map, \(\mathcal A\) one of its sides, \(I\) the number of vertices strictly inside \(\mathcal A\), and \(E_{\mathcal A}\) the number of edges both of whose darts lie in faces of \(\mathcal A\). Then
\[
I-E_{\mathcal A}+|\mathcal A|=1 .
\]

*Proof.* Let \(G_{\mathcal A}\) be the subgraph formed by \(C\), the vertices strictly inside \(\mathcal A\) and the edges counted by \(E_{\mathcal A}\); an end of such an edge that is not on \(C\) is strictly inside \(\mathcal A\) by Lemma 3.4(a), because the dart leaving it has its face in \(\mathcal A\), so this is a subgraph with \(I+h\) vertices and \(E_{\mathcal A}+h\) edges.

\(G_{\mathcal A}\) is connected: a shortest path in \(M\) from a vertex strictly inside \(\mathcal A\) to \(C\) uses, by Lemma 3.4(b), only vertices strictly inside \(\mathcal A\) and edges counted by \(E_{\mathcal A}\) before reaching \(C\).

For \(f\in\mathcal A\), every edge with a dart in \(f\) lies in \(C\) or is counted by \(E_{\mathcal A}\) (by Theorem 3.2), so \(b_f\in\mathcal Z(G_{\mathcal A})\). The vectors \(b_f\), \(f\in\mathcal A\), are linearly independent by Lemma 3.1(c), because \(\mathcal A\) is not the set of all faces. By Lemma 3.1(a),
\[
|\mathcal A|\le(E_{\mathcal A}+h)-(I+h)+1,
\]
that is, \(I-E_{\mathcal A}+|\mathcal A|\le1\).
The same holds for the other side \(\mathcal A'\). Every vertex not on \(C\) is strictly inside exactly one side (Lemma 3.4), and every edge not in \(C\) has both darts on one side (Theorem 3.2), so the two left-hand sides add up to \((V-h)-(E-h)+F=2\). Hence both equal \(1\). \(\square\)

## 4. Faces of a connected submap

Let \(K\) be a connected subgraph of the underlying graph of a sphere map \(M\), with at least one edge. With the rotations restricted to its darts, \(K\) is a map; it is a component of the map obtained from \(M\) by deleting all edges outside \(K\), so it is a sphere map by Proposition 1.6(e). Its faces can be read off from \(M\). Call two faces of \(M\) *\(K\)-adjacent* if some edge outside \(K\) has one dart in each, and call the classes of the equivalence relation generated by \(K\)-adjacency the *regions* of \(K\); they are the components of the graph obtained from the underlying graph of \(M^*\) by deleting the dual edges of the edges of \(K\).

**Proposition 4.1** (Regions). For a dart \(x\) of \(K\), let \(\rho(x)\) be the region containing the face of \(M\) on the left of \(x\). Two darts of \(K\) lie in the same face of \(K\) if and only if they have the same region, and every region arises in this way. Thus the faces of \(K\) correspond bijectively to its regions, the face of \(K\) corresponding to a region \(R\) consisting of the darts of \(K\) whose left face in \(M\) lies in \(R\).

*Proof.* *Consecutive darts have the same region.* Let \(x\) be a dart of \(K\) entering \(v\), and let \(y_1,\dots,y_j\) be the darts of \(M\) at \(v\) strictly between \(\theta x\) and the next dart of \(K\) in the rotation; then \(\varphi_K(x)=\sigma_M^{j+1}(\theta x)\). The face of \(x\) in \(M\) contains \(\varphi_M(x)=\sigma_M(\theta x)\); for each \(i\), the faces of \(y_i\) and \(\theta y_i\) are \(K\)-adjacent, and the face of \(\theta y_i\) contains \(\sigma_M(y_i)\). Hence \(\rho(x)=\rho(\varphi_K(x))\), and \(\rho\) is constant on every face of \(K\).

*There are at least as many regions as faces of \(K\).* A graph has at least as many components as its number of vertices minus its number of edges plus the dimension of its cycle space, and in fact exactly that many, by Lemma 3.1(a) applied to each component. The graph of regions has the \(F_M\) faces of \(M\) as vertices and \(E_M-E_K\) edges. For a vertex \(v\) of \(M\) not in \(K\), all edges at \(v\) lie outside \(K\), so the face boundary of \(M^*\) belonging to \(v\) lies in its cycle space; for the \(V_M-p\) vertices outside \(K\) (where \(p\) is the number of vertices of \(K\)) these vectors are independent by Lemma 3.1(c) applied to \(M^*\). Hence the number \(c\) of regions satisfies
\[
\begin{aligned}
c&\ge F_M-(E_M-E_K)+(V_M-p)\\
&=2-p+E_K=F_K .
\end{aligned}
\]

*Every region contains the left face of a dart of \(K\).* Otherwise every dart of every face of a region \(R\) belongs to an edge outside \(K\), whose other face is then also in \(R\); so \(R\) would be closed under adjacency in the connected graph of \(M^*\), hence contain all faces, including the face of a dart of \(K\).

So \(\rho\) induces a surjection from the faces of \(K\) onto the regions, and \(c\ge F_K\) makes it a bijection. \(\square\)

## 5. Plane embeddings

A *plane embedding* of a graph represents its vertices by distinct points of the sphere and its edges by arcs between them that meet only at common ends. For an embedding of a connected graph, the edge ends at each vertex are met in a cyclic order when one goes once around the vertex counterclockwise, and these cyclic orders form a rotation system.

**Theorem 5.1** (Embedding theorem; open obligation of this course). The rotation system of a plane embedding of a connected finite graph is a sphere map, and its faces are the boundary walks of the regions of the complement of the embedded graph.

This is the classical bridge from the topological notion of planarity to sphere maps; its proof rests on the Jordan curve theorem and is not given in this course. It is used only to pass from "planar" to "carries a sphere map". The theorem of the introduction, stated for graphs carrying a sphere map, and all other results of the course are proved in full here.

## 6. Exercises

**6.1.** Verify the faces listed in Example 1.3(c) for both rotation systems.

**6.2.** Show that in a sphere map with at least two edges, a loop is never a bridge, and its two darts lie in different faces.

**6.3.** Check Proposition 3.5 when \(C\) is the boundary of a single face \(f\) of length \(h\) whose boundary is a cycle and \(\mathcal A=\{f\}\).

**6.4.** In the octahedron, with vertices \(\pm e_1,\pm e_2,\pm e_3\) of \(\mathbb R^3\) and the rotation system of its surface, let \(C\) be the \(4\)-cycle through \(\pm e_1,\pm e_2\). Compute \(I\), \(E_{\mathcal A}\) and \(|\mathcal A|\) for both sides.

## 7. Solutions

**6.1.** With the first rotation system: \(\varphi(12)=\sigma(21)=24\), \(\varphi(24)=\sigma(42)=41\), \(\varphi(41)=\sigma(14)=12\), giving \((12,24,41)\); similarly for the other three faces, which together use all twelve darts. With \((21,23,24)\) at vertex \(2\): \(\varphi(12)=\sigma(21)=23\), \(\varphi(23)=\sigma(32)=34\), \(\varphi(34)=\sigma(43)=42\), \(\varphi(42)=\sigma(24)=21\), \(\varphi(21)=\sigma(12)=13\), \(\varphi(13)=\sigma(31)=32\), \(\varphi(32)=\sigma(23)=24\), \(\varphi(24)=\sigma(42)=41\), \(\varphi(41)=\sigma(14)=12\): one face of length \(9\), and the remaining darts \(14,43,31\) form a second face, so \(F=2\) and \(\chi=0\).

**6.2.** Deleting a loop does not disconnect the graph. By Proposition 1.6(c), its two darts lie in different faces.

**6.3.** By Theorem 3.2 the sides of \(C=b_f\) are \(\{f\}\) and the remaining faces. A vertex strictly inside \(\{f\}\) would have all faces around it equal to \(f\), and then all its edges would have both darts in \(f\), so \(f\) would contain darts not on \(C\); since the darts of \(f\) are exactly the \(h\) darts of \(C\) in one orientation, \(I=0\) and \(E_{\mathcal A}=0\). Then \(I-E_{\mathcal A}+|\mathcal A|=0-0+1=1\).

**6.4.** The octahedron has \(6\) vertices, \(12\) edges and \(8\) triangular faces. The cycle separates the four faces at \(e_3\) from the four faces at \(-e_3\). For the side at \(e_3\): \(I=1\) (the vertex \(e_3\)), \(E_{\mathcal A}=4\) (the edges at \(e_3\)) and \(|\mathcal A|=4\), so \(1-4+4=1\); the other side is symmetric.

## References

- [OpenAI-B] OpenAI, *Paired states and Hamiltonian cycles in cubic bipartite planar graphs*, OpenAI Math Release preprint, 24 September 2026. https://github.com/openai/math/blob/main/preprints/Paired-states-and-Hamiltonian-cycles-in-cubic-bipartite-planar-graphs-September-24-2026/paper.pdf
- [APSW] H. Alt, M. S. Payne, J. M. Schmidt and D. R. Wood, *Thoughts on Barnette's conjecture*, Australasian Journal of Combinatorics 64 (2016), 354–365. https://arxiv.org/abs/1312.3783
- [GSW] M. Gorsky, R. Steiner and S. Wiederrecht, *Matching theory and Barnette's conjecture*, Discrete Mathematics 346 (2023), 113249. https://arxiv.org/abs/2202.11641
- [FS] T. Feder and C. Subi, *On Barnette's conjecture*, ECCC report TR06-015, 2006. https://eccc.weizmann.ac.il/report/2006/015/
- [Kar] F. Kardoš, *A computer-assisted proof of the Barnette–Goodey conjecture: not only fullerene graphs are Hamiltonian*, SIAM Journal on Discrete Mathematics 34 (2020), 62–100. https://arxiv.org/abs/1409.2440
- [Sch] T. Schnieders, *Barnette graphs with faces up to size 8 are Hamiltonian*, 2025. https://arxiv.org/abs/2508.03531