**Context:** Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my perspective, it doesn't seem too impressive, the argument is rather elementary, but I can't find another paper which states what I found. The closest I could find was Jan Florek's [On Barnette's Conjecture][1], which is about a subcase which I was previously aware of.

**Definitions:** It is well-known that a cubic polyhedral graph, $P$, is Hamiltonian iff its dual, $D$, can be partitioned into two sets of vertices, $A,B$, such that the induced subgraphs $D[A]$ and $D[B]$ are both trees. A dual with this condition is said to have a *tree-partitioning*.

Since a dual, $D$, of cubic bipartite polyhedral graph is triangularized, and has a unique 3-coloring, I found it easier to think about removing all vertices in one color class, which gives us a 2-connected bipartite graph, $S$, with a fixed planar embedding. To recover $D$ from $S$, for each face, $f$ in $S$, we add a vertex $v_f$, and add edges between $v_f$ and all vertices $u$ incident to $f$. This recovery process is well defined, and shall be denoted as $D(S)$.

**My result says:** if a bipartite 2-connected planar embedded graph, $S$, is constructible (in a way defined below), then $D(S)$ has a tree partitioning, and thus is the dual of a Hamiltonian bipartite cubic polyhedral graph.

**Construction Method:** 

Throughout, the "exterior cycle" of a connected component is the cycle that creates a polygon with the largest area with respect to how the component is embedded. 
 
 1. We start with $S_1$ being an even cycle graph $C_{2k_0}$, with a planar embedding. Currently, all vertices of $S_1$ make up its "exterior cycle".
 2. If the exterior cycle has four vertices, we may choose to stop at $S_i$, or may continue
 3. Embed a new even cycle graph $C_{2k_i}$ as a new component, such that all vertices are outside the exterior cycle of $S_i$
 4. Choose two paths of length $2 \leq l \leq 4 $ along the exterior cycles of your two components, $p_1 = v_1,v_2 \dots v_l, p_2 = u_1,u_2,\dots u_l$.
 5. Add edges $(v_j,u_j)$ for all $1 \leq j \leq l$, and contract said edges. (moving the location of $u_j$ to $v_j$ in the embedding)
 6. Return to step 2.

 
Any $S_i$ at which we can stop at step 2, is constructible. My result above is gotten from a rather simple inductive argument. The class of graphs which are made Hamiltonian contains those proven by Florek, in fact, this is specifically the case when $k_i = 2$ for $i > 0$, and one may use a even shorter argument for this case.

Is this result known, and if not, does the fact that the family of graphs is rather difficult to describe detract from its value?

**Edit:** I just realized that there is an second result of my methods. If $P$ is a cubic bipartite polyhedral graph, and also constructible, then $P$ is Hamiltonian. 

While I am aware that there are non 2-connected bipartite planar graphs, such as the tetrahedron with all edges subdivided, I cannot immediately come up with any non-constructible graphs that are also cubic and polyhedral.

**Second edit:** On further thought, an example is the (unique) cubic polyhedral graph with 6 squares and 3 hexagons. (constructed by having 2 clumps of 3 pairwise incident squares divided by a ring of hexagons)
  [1]: https://www.sciencedirect.com/science/article/pii/S0012365X10000403