2026-10-29 09:13 UTC
A positive resolution of Barnette's conjecture is among the results in the openai dump.
It says that every 3-connected cubic bipartite planar graph has a Hamiltonian cycle.
Tutte conjectured that every 3-connected cubic bipartite graph has a Hamiltonian cycle (i.e., the same conditions above except planarity). That conjecture is false.
But the counterexamples to that conjecture of Tutte's are quite large (originally around 90 vertices, eventually down to around 50) and in particular, they have high genus. A quite recent search found none with genus less than 4: https://arxiv.org/abs/2101.00943v2
The proof of Barnette is non-constructive and (unsurprisingly) not very human-readable. It might also be worth saying that, unless I am mistaken, the result does not come with a lean proof.
So maybe I am getting ahead of myself but tying down the exact genus where the conjecture fails would be quite interesting to me.
#math #graphTheory #openai
Replies (0)
No replies.