Approximating Barnette’s Conjecture

Since Hamiltonicity in a planar graph is equivalent to admitting a $2$-page book embedding with all consecutive vertices (including the first and the last) connected, studying subhamiltonian cycles (that is, linear vertex orders in such embeddings) offers a relaxed yet meaningful perspective. In this context, it is known that every $n$-vertex Barnette graph admits a subhamiltonian cycle containing at least $\frac{2n}{3}$ edges [1]. Building on this, we revisit and refine the approach of [1], improve the bound to $\frac{5n}{6}$, and discuss its potentials as a step toward resolving Barnette’s conjecture. Note that a bound of $n$ settles the conjecture.

We assume familiarity with basic concepts from Graph Theory and Graph Drawing. A $k$-page book embedding of a graph defines an order of its vertices and partitions its edges into $k$ sets of non-crossing edges. A graph admitting a $2$-page book embedding is called subhamiltonian, as it can be augmented to Hamiltonian by adding edges between consecutive vertices. The vertex order of such an embedding is called a subhamiltonian cycle.

As mentioned, all Barnette graphs can be constructed by iteratively applying two operations, cube-expansions and $C_4$-expansions, starting from the cube graph (see Figure 1). In a cube-expansion, a vertex $x$ is replaced by seven new vertices $x_1,\mathrm{\dots },x_7$ and the following edges: $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$, $(x_1,x_4)$, $(x_1,x_5)$, $(x_4,x_6)$, $(x_5,x_6)$, $(x_2,x_4)$, $(x_2,x_7)$, $(x_3,x_7)$, $(x_6,x_7)$, and $(x_3,x_5)$, where $y_1$, $y_2$, and $y_3$ are the neighbors of $x$. In a $C_4$-expansion, two edges $e_1$ and $e_2$ with an odd distance along the boundary of a face are each subdivided twice, and the resulting new vertices are connected with two additional edges by preserving both planarity and bipartiteness.

Let $G$ be an embedded Barnette graph with $n$ vertices. By Lemma 2 of [1], the edges and the faces of $G$ can be colored with three colors (red, blue and green) with the following properties (refer to Fig. 3(a) of [1] for an illustration): (i) every facial cycle of $G$ is bichromatic, i.e., its edges alternate between two colors along its boundary, (ii) no two neighboring faces are of the same color, (iii) every face of $G$ is colored differently from its bounding edges, (iv) the edge that bounds two faces of $G$ colored $x$ and $y$ is of color $z$, where $\{x,y,z\}=\{\text{red},\text{blue},\text{green}\}$, (v) the subgraph $G_{bg}^{\ast }$ of the dual $G^{\ast }$ of $G$ induced by the blue and green faces of $G$ is connected. Let ${𝒯}_{bg}^{\ast }$ be a spanning tree of $G_{bg}^{\ast }$. This tree together with property (iv) yields a partition of the red edges of $G$ into those that are crossed by ${𝒯}_{bg}^{\ast }$ (corresponding to those belonging to ${𝒯}_{bg}^{\ast }$) and the remaining ones that are not crossed by ${𝒯}_{bg}^{\ast }$. Then, the algorithm by Alam et al. [1] computes a subhamiltonian cycle $C$ of $G$ by a traversal of ${𝒯}_{bg}^{\ast }$, assuming that ${𝒯}_{bg}^{\ast }$ is rooted at an arbitrary blue leaf $\rho$ as follows. For an arbitrary edge $(u,v)$ of $G$ that is crossed by ${𝒯}_{bg}^{\ast }$, let $p$ and $q$ be the faces that are bounded by $(u,v)$, that is, $(p,q)$ is an edge of ${𝒯}_{bg}^{\ast }$. The removal of $(p,q)$ from ${𝒯}_{bg}^{\ast }$ results in two trees ${𝒯}_p^{\ast }$ and ${𝒯}_q^{\ast }$, such that w.l.o.g. $\rho$ belongs to ${𝒯}_p^{\ast }$. For the recursive step, it is assumed that a simple and plane subhamiltonian cycle $C_p$ for the subgraph $G_p$ of $G$ induced by the vertices of the faces of $G$ in ${𝒯}_p^{\ast }$ has been computed, which does not necessarily span all vertices of $G_p$, but it satisfies the following invariant properties:

1. I.1

   The edge $(u,v)$ is on $C_p$.

2. I.2

   Every red edge of $G_p$ is in the interior of $C_p$ or on $C_p$.

3. I.3

   Every blue edge of $G_p$ is in the exterior of $C_p$ or on $C_p$.

4. I.4

   Every green edge of $G_p$ is on $C_p$.

5. I.5

   For every red edge $e$ of $G_p$ that is not crossed by ${𝒯}_{bg}^{\ast }$ and that is adjacent to two faces $h$ and $h^{\prime }$ of $G$, with $h\in {𝒯}_p^{\ast }$ and $h^{\prime }\notin {𝒯}_p^{\ast }$, one of the following holds:

   1. (a)

      if $h$ is a blue face, then both endpoints of $e$ are on $C_p$,

   2. (b)

      if $h$ is a green face, then none of the endpoints of $e$ is on $C_p$.

Depending on the colors of faces $p$ and $q$, the traversal of ${𝒯}_{bg}^{\ast }$ is continued by extending the cycle $C_p$ to vertices of face $q$ (thus obtaining a new cycle ${𝒞}_q$) and by maintaining Invariants I.1-I.5 as illustrated in Figure 2. Once the traversal of ${𝒯}_{bg}^{\ast }$ has been completed, a simple and plane cycle $𝒞$ has been computed, in which, by Invariants I.2-I.4, every green edge of $G$ is on $𝒞$, while every red (blue) edge of $G$ is in the interior (exterior) of cycle $𝒞$ or on $𝒞$. Since ${𝒯}_{bg}^{\ast }$ is a spanning tree of $G_{bg}^{\ast }$, every green edge of $G$ bounds a face that is in ${𝒯}_{bg}^{\ast }$, and by Invariant I.4 both its endpoints are consecutive along $𝒞$. As every vertex is incident to a green edge, it follow that cycle $𝒞$ is indeed subhamiltonian. The following properties directly follow from Invariants I.4 and I.5, respectively (see [1]).

The authors in [1] used Properties 1 and 2 to show that every Barnette graph admits a subhamiltonian cycle with $\frac{2n}{3}$ edges.

Let $f_g$ be a green face of $G$ which contains a blue edge $e_b$ appearing between two consecutive red edges $e_r$ and $e_r^{\prime }$ of $f_g$ that are crossed by ${𝒯}_{bg}^{\ast }$. Since $e_r$ and $e_r^{\prime }$ are crossed by ${𝒯}_{bg}^{\ast }$, after the algorithm processes face $f_g$ in the traversal of ${𝒯}_{bg}^{\ast }$, by Invariant I.1 both edges $e_r$ and $e_r^{\prime }$ are on the subhamiltonian cycle constructed so far. By Invariant I.3, $e_b$ is either in the exterior or on the subhamiltonian cycle constructed so far. Since $e_b$ appears between $e_r$ and $e_r^{\prime }$ along $f_g$, it follows that $e_b$ cannot be in its exterior. Since the subhamiltonian cycle is not extended along blue edges (as those are not crossed by ${𝒯}_{bg}^{\ast }$), $e_b$ will be part of $𝒞$. $◀$

Let $f_g$ be a green face of $G$ that corresponds to a leaf of ${𝒯}_{bg}^{\ast }$ and let $f_b$ be its parent in ${𝒯}_{bg}^{\ast }$. Just before the algorithm processes face $f_g$ in the traversal of ${𝒯}_{bg}^{\ast }$, the red edge of $G$ that is crossed by the edge $(f_g,f_b)$ of ${𝒯}_{bg}^{\ast }$ necessarily belongs to the subhamiltonian cycle constructed so far by Invariant I.1. Since $f_g$ is a leaf of ${𝒯}_{bg}^{\ast }$ and since $f_g$ is green, the subhamiltonian cycle will not be extended any further after the algorithm processes face $f_g$ by Invariant I.5b. Hence, the red edge of $G$ that is crossed by the edge $(f_g,f_b)$ of ${𝒯}_{bg}^{\ast }$ will remain on the subhamiltonian cycle as desired. $◀$

Let $f_g$ be a green $4$-face (i.e., of degree $4$) of $G$ and assume that $f_g$ does not correspond to a leaf of ${𝒯}_{bg}^{\ast }$. Since $f_g$ is a $4$-face of $G$, it consists of two red and two blue edges that alternate along its boundary. Since $f_g$ does not correspond to a leaf of ${𝒯}_{bg}^{\ast }$, both red edges are crossed by ${𝒯}_{bg}^{\ast }$. Now the statement directly follows from Property 3. $◀$

Let $f_g$ be a green $6$-face of $G$ that does not correspond to a leaf of ${𝒯}_{bg}^{\ast }$. Hence, its boundary contains at least two red edges that are crossed by ${𝒯}_{bg}^{\ast }$. These two red edges are consecutive on the boundary of $f_g$ and thus the result follows by Property 3. $◀$ So far, ${𝒯}_{bg}^{\ast }$ has only been assumed to be a spanning tree of $G_{bg}^{\ast }$. In the following, we show that it can be chosen in such a way that the preceding property generalizes to all green faces.

Let $f_g$ be a green face of $G$ that is not a leaf in ${𝒯}_{bg}^{\ast }$. Since $f_g$ is not a leaf, its boundary contains at least two red edges that are crossed by ${𝒯}_{bg}^{\ast }$. Our goal is to locally modify ${𝒯}_{bg}^{\ast }$ so that these two red edges appear consecutively along the boundary of $f_g$; Once this goal is achieved, we can apply Property 3 to obtain the desired result. Denote by $r_1,\mathrm{\dots },r_k$ the red edges on the boundary of $f_g$ in clockwise order. Let also $e_1,\mathrm{\dots },e_k$ be the corresponding dual edges of $G_{bg}^{\ast }$. Finally, denote by $v_g$ the vertex of $G_{bg}^{\ast }$ corresponding to $f_g$. W.l.o.g. assume that $r_1$ is crossed by ${𝒯}_{bg}^{\ast }$, that is, $e_1$ belongs to ${𝒯}_{bg}^{\ast }$. Let $r_j$ be the edge on the boundary of $f$ that is crossed by ${𝒯}_{bg}^{\ast }$, such that $j>1$ and $j$ is minimum. Note that $r_j$ exists, because $f_g$ is not a leaf in ${𝒯}_{bg}^{\ast }$. If $j=2$ or $j=k$ holds, then $r_1$ and $r_2$ are consecutive and we are done. Thus, assume . Consider the graph ${𝒯}_{bg}^{\ast }+e_2$. Since ${𝒯}_{bg}^{\ast }$ is spanning, ${𝒯}_{bg}^{\ast }+e_2$ contains a cycle. Let $e$ be the edge of this cycle (distinct from $e_2$) that is also incident to $v_g$. If $e\ne e_1$, then replacing $e$ with $e_2$ in ${𝒯}_{bg}^{\ast }$ yields a new spanning tree in which $e_1$ and $e_2$ are consecutive, as desired. Hence, suppose $e=e_1$. In this case, we obtain a new spanning tree by replacing $e_1$ with $e_2$ in ${𝒯}_{bg}^{\ast }$ and we observe that the distance between the relevant pair of red edges crossed by this tree has been decreased. Repeating this argument a finite number of times will eventually yield a configuration in which the two red edges are consecutive, completing the proof. $◀$ We are now ready to prove the main theorem of this section.

Let $G$ be an $n$-vertex Barnette graph and let $F_g$, $F_r$ and $F_b$ be the set of green, red and blue faces of $G$, respectively. Since $G$ is $3$-regular, Euler’s formula directly yields that $G$ has (i) $\frac{3n}{2}$ edges out of which $\frac{n}{2}$ are green, $\frac{n}{2}$ are red and $\frac{n}{2}$ are blue, and (ii) $\frac{n}{2}+2$ faces. Hence, $|F_g|+|F_r|+|F_b|=\frac{n}{2}+2$. Assume w.l.o.g. that $|F_g|\ge |F_r|\ge |F_b|$. By this assumption, $F_g$ contains at least $\frac{1}{3}(\frac{n}{2}+2)$ faces. Thus, for some $x>0$, we may write:

Since $|F_g|\ge |F_r|\ge |F_b|$, it follows:

We next claim that the average degree of the faces in $F_g$ is at most $6$. To see this, observe that edges on the boundary of the faces of $F_g$ are in total $n$, since by Properties (iii) and (iv) of the edge coloring of $G$, they correspond to the red and the blue edges of $G$. Thus, by Eq.(1) the average degree of the faces in $F_g$ is $\frac{n}{\frac{n}{6}+x}$, which is at most $6$ as claimed. It follows that for every face in $F_g$ of degree greater than $6$, there is at least one face in $F_g$ which has degree $4$. With these observations in mind, we are now ready to count the number of edges contained in the subhamiltonian cycle $𝒞$.

• $\mathrm{■}$

  By Property 1, subhamiltonian cycle $𝒞$ contains all green edges of $G$, which are $\frac{n}{2}$ in total.

• $\mathrm{■}$

  By Property 2, subhamiltonian cycle $𝒞$ contains all red edges of $G$ not crossed by ${𝒯}_{bg}^{\ast }$. We claim that these are at least $\frac{n}{6}-\frac{x}{2}$. To see this, recall that all red edges of $G$ are $\frac{n}{2}$ in total. Since ${𝒯}_{bg}^{\ast }$ is a spanning tree of ${𝒢}_{bg}^{\ast }$, the number of red edges crossed by ${𝒯}_{bg}^{\ast }$ is:

  $$|F_b|+|F_g|-1=\frac{n}{2}+2-|F_r|-1=\frac{n}{2}-|F_r|+1.$$

  Therefore, the number of red edges of $G$ which are not crossed by ${𝒯}_{bg}^{\ast }$ is:

  $$\frac{n}{2}-(\frac{n}{2}-|F_r|+1)=|F_r|-1\stackrel{\text{(}\text{<a href="\#S3.E2" title="Equation 2 ‣ Proof. ‣ 3 Our Main Result ‣ Approximating Barnette’s Conjecture" class="ltx\_ref"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}\text{)}}{\ge }\frac{n}{6}-\frac{x}{2}$$

• $\mathrm{■}$

  Each green face of $G$ contributes an additional edge to $𝒞$. To see this, observe that a green face corresponding to leaf in ${𝒯}_{bg}^{\ast }$ contributes at least one (red) edge to $𝒞$ by Property 4. Each of the remaining faces contributes at least one (blue) edge by Properties 5 and 7.

From the discussion above, it follows that the number of edges belonging to the subhamiltonian cycle $𝒞$ is at least

which concludes the proof. $◀$

A green leaf $f$ contains exactly $\frac{1}{2}|f|$ red edges, one of which is crossed by ${𝒯}_{bg}^{\ast }$. The crossed edge will be part of $𝒞$ due to Property 4, while the others are part of $𝒞$ by construction. A green non-leaf $f$ has, by assumption, maximum degree in ${𝒯}_{bg}^{\ast }$, i.e., all its red edges are crossed by ${𝒯}_{bg}^{\ast }$. But then Property 3 directly implies that $\frac{1}{2}|f|$ blue edges of $f$ are part of $𝒞$. Hence, for any green face, half of its boundary edges are part of $𝒞$. Since the faces in $F_g$ are disjoint and cover all red and blue edges, they include exactly $n$ edges. Summing over all green faces, this contributes a total of $n/2$ edges to $𝒞$. Together with all green edges (which are $n/2$ many), this means that $|𝒞|=n$ and thus $G$ is Hamiltonian. $◀$ The following known result from the literature due to Florek [6] can hence be obtained as a direct corollary of Observation 2.

W.l.o.g. let all green faces have degree $4$. Hence, a green face is either a leaf in ${𝒯}_{bg}^{\ast }$ or its degree is $2$ in ${𝒯}_{bg}^{\ast }$, i.e., maximum. Thus, Observation 2 yields the desired result. $◀$