Barnette’s Conjecture for Humans, Part 1

If you are familiar with my blog you know I’m a bit obsessed with the Graceful Tree Conjecture, but my second favorite graph theory conjecture is (was?) Barnette’s conjecture. It got promoted to a theorem in the 6-Oct-2026 Mathocalypse. In this post I’ll explain the conjecture, and, in part, the proof. I’ll finish my exposition of the proof in a follow-up post.

When I first flipped through the OpenAI proof, I thought, Hey, this looks reasonable, I should be able to handle it. It ended up taking me several weekends. The paper is strangely dense and has an awkward overall flow, and it has only one pathetic little figure, despite being a proof that lends itself to visuals. So I felt motivated to write this post.

First, a quick refresher: a Hamiltonian cycle is a walk along the edges of a graph that visits every vertex exactly once and ends up back where it started. A graph that has one is Hamiltonian. Here are three Hamiltonian graphs, each with a Hamiltonian cycle in blue:

A dodecahedron, a cube, and an irregular graph, drawn flat, each with a Hamiltonian cycle in blue.

It’s a bit tricky to look at a graph and quickly determine if it is Hamiltonian, which makes it an interesting area of study. There are, however, a few well-known facts. For example, Dirac’s theorem says that a graph is Hamiltonian if every vertex has enough neighbors (see my previous post).

Outside of Dirac’s theorem and its descendants, there are disappointingly few easy-to-state theorems for recognizing Hamiltonian graphs. Here’s a famous exception:

Every 4-connected planar graph is Hamiltonian.

A graph is planar if you can draw it without any of its edges crossing, and it’s 4-connected if it stays connected after you remove any 3 of its vertices.

Likewise, a graph is 3-connected if it stays connected after you remove any 2 of its vertices. Every 4-connected graph is 3-connected, but not the other way around. In the following figure, the cube on the left is 3-connected but not 4-connected: remove the three circled vertices, and the vertex they surround is cut off from the rest. The octahedron on the right is 4-connected.

On the left, a cube drawn flat, with the three neighbors of one inner corner circled in orange. On the right, an octahedron drawn flat.

Barnette’s conjecture is exciting because it’s the same rare kind of statement as Tutte’s, and stood open for 57 years:

Every 3-connected planar graph that is cubic and bipartite is Hamiltonian.

A graph is cubic if every vertex has exactly three edges. It’s bipartite if you can color its vertices black and white, such that every edge joins a black vertex to a white one. A graph that’s 3-connected, planar, cubic, and bipartite is a Barnette graph.

There’s some drama behind that list of four properties. Leave out “bipartite” and you get Tait’s conjecture, from 1884, which would have proven the four color theorem if it were true. It stood for 62 years, until Tutte found a counterexample. Tutte then made a conjecture of his own, which leaves out “planar” instead, and by 1976 Horton had sunk that one with a counterexample. Barnette’s conjecture has both qualifiers and has stood the test of time.

By the way, another way of saying 3-connected planar graph is “convex polyhedron” (Steinitz’s theorem). Here are four polyhedra, each with a Hamiltonian cycle in blue:

A cube, a hexagonal prism, a truncated octahedron, and a truncated cuboctahedron, each with a blue Hamiltonian cycle.

There’s another way to recognize a bipartite graph. Walk around a cycle in one and the two colors alternate. You arrive back where you started after an even number of steps, so every cycle must have even length, including the one around each face. In a planar graph, it works the other way too: if every face has an even number of sides, then the graph is bipartite.

In the following figure, the graph on the left is bipartite. The graph on the right isn’t: it has a face with three sides.

Two cubic graphs with black and white vertices, where an orange triangle in the second leaves two vertices red.

So, here’s another way of stating Barnette’s conjecture:

If a convex polyhedron has 3 edges at each corner, and every face has an even number of sides, then it must have a Hamiltonian cycle.

On the way to a proof, we’re going to reformulate the conjecture yet again, but first let’s take a step back and gaze upon the overall proof strategy:

This post will cover everything in the above chart except the Prime branch, which is where the juicy new stuff lives, so we’ll defer it to Part 2.

You might be wondering what a “harlequin” is; we’ll cover that later in this post. It’s just some made-up terminology that I think makes the proof easier to digest, especially in Part 2.

1. Dual reformulation

We’ve already restated the conjecture once, now let’s do it again by examining the dual of a Barnette graph (put a vertex in each face, and join two vertices whenever their faces share an edge).

Before taking a dual, let’s see what a Hamiltonian cycle does to the faces of a polyhedron. Take the truncated octahedron from earlier. Its Hamiltonian cycle is a closed loop, so it cuts the surface of the polyhedron into two pieces. Drag the slider under the following video to cut it open.

On the left of the next figure, the same polyhedron is flattened, with the faces inside its cycle tinted. Drag the slider to stretch the inside and outside into round disks, with the cycle around each rim.

Every vertex lies on the cycle, and the graph is cubic, so every vertex has exactly one edge that isn’t part of the cycle. Those leftover edges are chords. Two chords never cross, because planar drawings do not have crossings. The region around the outside of the flat drawing is also a face, and it ends up in the middle of the right disk.

Now put a vertex in each face of a disk, and join two vertices whenever their faces share a chord. Every chord cuts its disk in two, so there’s exactly one route from any face to any other. That makes both of these graphs trees, which are connected graphs that have no cycles.

The dual of any cubic planar graph is a triangulation. Below are two triangulations, which are duals of Barnette graphs. Each is depicted with a blue Hamiltonian cycle from its source graph, and the two trees resulting from the cut.

Two triangulations drawn flat, each with a green tree, a purple tree, and a blue loop between them.

So a Hamiltonian cycle makes two trees. It works the other way, too:

A cubic polyhedral graph has a Hamiltonian cycle if and only if you can color the vertices of its dual triangulation green and purple, such that each color induces a tree.

Sherman Stein proved this at UC Davis, a couple of years after his colleague David Barnette made his conjecture. We’ve already seen how the easy direction works, from a Hamiltonian cycle to two trees. The other direction is a bit trickier, but Stein proved it too.

That gives us Barnette’s conjecture in terms of the dual: the vertices of the dual of every Barnette graph can be colored green and purple, such that each color induces a tree.

Nothing so far is new, but it’s all necessary to understand the OpenAI proof.

2. Harlequins and root triangles

The face-colored dual of a Barnette graph is so central to the proof that it deserves a name:

A harlequin is a polyhedron whose faces are all triangles, colored black and white so that every edge has a black triangle on one side and a white one on the other.

Every harlequin is the dual of a Barnette graph, and vice versa. Here are the earlier four polyhedra again, with their corners colored black and white. Under each one is its dual harlequin, first in 3D, then flat.

Three rows: four polyhedra, their duals in black and white triangles, and the duals drawn flat as harlequins.

Every harlequin can be flattened the same way: pick a black triangle, poke a hole in it, and stretch it out. The gray band around each of the above 2D drawings is the black triangle with the hole, which now goes around the outside.

Let’s call that black triangle the root triangle. Any black triangle can be the root triangle.

The harlequin colors aren’t decoration, by the way. They’re the “bipartite” in Barnette’s conjecture. This post uses those colors only once, when we cut a harlequin in two, but Part 2 leans on them constantly.

3. Strengthening the conjecture

In 1986, the Soviet mathematician Alexander Kelmans showed that Barnette’s conjecture is equivalent to something stronger: every edge of every Barnette graph is skipped by some Hamiltonian cycle.

For example, take the cube. Here are all six of its Hamiltonian cycles:

The cube's graph drawn six times in a row, each time with a different Hamiltonian cycle in blue.

Pick any edge, and in at least one drawing, it’s gray.

A Hamiltonian cycle skips an edge exactly when the edge of the harlequin that crosses it is in one of the two trees. You can see this in the two triangulations from earlier, where the blue loops never cross a green or purple edge. If we combine Kelmans’s theorem with Stein’s, in our harlequin language, we get:

For every harlequin and every edge of , the vertices of can be colored green and purple such that each color induces a tree, and is in one of the two trees.

Not just any pair of trees will do, though. The following figure shows a harlequin colored two ways, each from a Hamiltonian cycle of its dual. On the left, the edge , a side of the tinted triangle, joins a purple vertex to a green one, so it isn’t in either tree. It takes a different Hamiltonian cycle to get the trees on the right, where is in the green one.

A lopsided harlequin twice, with green and purple trees that leave out the edge e, and with trees that contain it.

So the coloring on the left is not the kind that the conjecture asks for, at least not for this edge : each color induces a tree, but is in neither one. The coloring on the right is.

4. Separating triangles

A separating triangle is a 3-cycle that is not a face. In the following figure, the harlequin on the left has no separating triangle: every loop of three edges is the outline of a face, even the one around the outside, which is the root triangle. The other two each have a separating triangle, in orange, with vertices both inside and outside of it.

Three harlequins drawn flat, the second and third each with a separating triangle in orange.

The proof of the harlequin version of Barnette’s conjecture splits into two cases, depending on whether a harlequin has a separating triangle. A harlequin that has one is composite, and a harlequin that doesn’t is prime.

A separating triangle cuts the harlequin in two, with vertices on both sides, so a composite harlequin comes apart into two smaller pieces.

5. Composite harlequins: proof by induction

Let’s check where we are in the flow chart. We’re trying to prove the harlequin version of Barnette’s conjecture: for every edge of a harlequin, its vertices can be colored green and purple so that each color induces a tree, and is in one of the two trees. We’ve reached the chart’s question, “Is it composite?”, and this section takes the composite branch. More specifically, here’s what we’ll prove in this section:

Cut a composite harlequin in two along a separating triangle. Suppose that, for every edge of either child, that child’s vertices can be colored green and purple so that each color induces a tree, and is in one of the two trees. Then the same goes for every edge of .

The plan is to cut in two along a separating triangle, color each piece green and purple, and glue the pieces back together. The two pieces have to agree on the colors of the separating triangle’s corners, and that’s where Kelmans’s strengthening comes in handy.

Cutting a Barnette graph this way is an old trick: Holton, Manvel, and McKay did it in 1985.

Here’s an illustration of a composite harlequin being cut into two smaller harlequins:

A composite harlequin above its two children, the outer and the inner, split at an orange separating triangle.

First, a fact about colors: the three triangles just outside a separating triangle always have the same color, and the three just inside have the other color. This is a known result, and can be proven with a simple counting argument.

Which color ends up outside depends on where the root triangle is. Any black triangle can be the root. From here on, we’ll always pick the root so that the three triangles just outside the separating triangle are black, like in the figure above.

Cutting along the separating triangle gives two children:

Either way, the cut leaves a hole with three edges around it, and one new triangle fills the hole:

Let be a composite harlequin, cut in two along a separating triangle. The patch of each child is the triangle whose three sides are the sides of the separating triangle.

Both patches are outlined in orange above. The outer child’s patch is the small triangle in the middle of its drawing. The inner child’s patch goes around the outside of its drawing, which makes it the root triangle.

The outer child’s patch borders the three black triangles just outside the separating triangle, so it’s white. The inner child’s patch borders the three white triangles just inside, so it’s black, which is just what a root triangle should be. Every edge still straddles a black triangle and a white one. That makes both children harlequins.

Color each child’s vertices green and purple, so that each color induces a tree:

Green and purple trees of the outer and inner children, glued into trees of the composite harlequin, with e in the green one.

Exactly one side of every triangle is in a tree, since its three corners can’t all share a color, or they’d make a cycle. That includes each child’s patch.

On the left of the above figure is the outer child, colored so that the edge is in its green tree. One side of its patch is in the green tree too: call it , and the third corner .

In the middle drawing is the inner child, where is a side of the patch too. It’s colored so that is in one of its trees, which is what the strengthening is for. Swap its colors if need be, so that tree is green too.

Then glue them, as in the right drawing. The purple trees meet only at , so together they’re one tree. The green trees meet along , the only path from to in either one, so together they’re one tree too, with in it.

That sets up an induction on the number of vertices. Suppose that every prime harlequin can be colored like that, for each of its edges. Then every composite harlequin can too: cut it in two, color its children by induction, and glue.

So now the harlequin version of Barnette’s conjecture comes down to the prime harlequins, and that’s what Part 2 of this post will be all about. Stay tuned!

6. References