Putting Tutte's counterexample to Tait's conjecture in perspective to hamiltonicity and non-hamiltonicity in certain planar cubic graphs

Enrico Iurlano; G\"unther R. Raidl; Herbert Fleischner

arxiv: 2510.08310 · v1 · submitted 2025-10-09 · 🧮 math.CO

Putting Tutte's counterexample to Tait's conjecture in perspective to hamiltonicity and non-hamiltonicity in certain planar cubic graphs

Herbert Fleischner , Enrico Iurlano , G\"unther R. Raidl This is my paper

Pith reviewed 2026-05-18 08:37 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C4505C10

keywords Tutte graphTait conjectureHamiltonian cyclesplanar cubic graphsTutte fragmentsprism graphscounterexamplesHolton-McKay

0 comments

The pith

Tutte's counterexample is positioned as a minimal element in an infinite family of hamiltonian and non-hamiltonian planar cubic graphs built from prisms and Tutte fragments.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an infinite family of planar cubic graphs by combining prism graphs with Tutte fragments. In this family Tutte's counterexample to Tait's conjecture functions as a minimal element with respect to the presence or absence of Hamiltonian cycles. Generalizations of the smallest known counterexamples due to Holton and McKay are also contained in the same family. The construction supplies a single perspective that organizes both Hamiltonian and non-Hamiltonian members of this graph class.

Core claim

Combinations of prism graphs and Tutte fragments generate an infinite family of planar cubic graphs in which Tutte's graph appears, in a certain sense, as the smallest non-Hamiltonian member while the family also contains Hamiltonian graphs and includes generalizations of the minimum-cardinality counterexamples of Holton and McKay.

What carries the argument

Recursive or iterative combinations of prism graphs and Tutte fragments that preserve the Hamiltonian or non-Hamiltonian property and embed Tutte's graph as the minimal element.

If this is right

The family unifies Tutte's counterexample with generalizations of the Holton-McKay minimal counterexamples under one construction.
Both Hamiltonian and non-Hamiltonian planar cubic graphs can be generated systematically by the same combination process.
Tutte's graph is the smallest non-Hamiltonian member within the family.
The construction places known examples and counterexamples to Tait's conjecture into a common structural context.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The family may serve as a generator for testing algorithms that decide Hamiltonicity on larger planar cubic graphs built by the same rules.
Similar recursive constructions could be explored for other conjectures involving cycles in planar graphs.
Determining whether every minimal non-Hamiltonian planar cubic graph belongs to this family would be a natural follow-up question.

Load-bearing premise

The specific rules for combining prisms and Tutte fragments preserve the required Hamiltonian or non-Hamiltonian property and correctly position Tutte's graph as minimal.

What would settle it

Discovery of a smaller non-Hamiltonian planar cubic graph that cannot be obtained by the stated combination rules, or verification that some graph produced by the rules is actually Hamiltonian when the construction claims it is not.

read the original abstract

Using the graphs of prisms and Tutte Fragments, we construct an infinite family of hamiltonian and non-hamiltonian graphs in which Tutte's counterexample to Tait's conjecture appears in a certain sense as a minimal element. We observe that generalizations of the minimum-cardinality counterexamples of Holton and McKay to Tait's conjecture are as well contained in this family.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper builds an explicit infinite family from prisms and Tutte fragments that places Tutte's graph as the minimal non-Hamiltonian member and also contains the Holton-McKay generalizations.

read the letter

This paper's main contribution is an explicit infinite family of planar cubic graphs built from prisms and Tutte fragments. In this family, Tutte's famous counterexample to Tait's conjecture sits as a minimal non-Hamiltonian member, and it also contains generalizations of the smallest counterexamples found by Holton and McKay. They do a good job laying out the construction rules and proving that the Hamiltonian or non-Hamiltonian property is preserved under the attachments. The arguments rely on exhaustive case analysis for paths through the three connection vertices, which keeps things self-contained and doesn't lean on heavy external theorems. The soft spots are minor. The minimality of Tutte's graph in the family rests on checking that smaller combinations don't produce earlier non-Hamiltonian examples, and while the paper claims to do this, a referee might want to see the base cases spelled out clearly in a figure or table. No major gaps jump out from the description. This work is aimed at graph theorists focused on Hamiltonicity in cubic planar graphs. Someone already familiar with Tutte's example and the history of Tait's conjecture would find the unifying family useful for generating more examples. It deserves peer review. The construction is concrete enough that referees can verify the details without too much trouble.

Referee Report

0 major / 3 minor

Summary. The manuscript constructs an infinite family of planar cubic graphs by recursively combining prisms with Tutte fragments. It positions Tutte's counterexample to Tait's conjecture as a minimal non-hamiltonian element within this family (in a specified sense) and shows that generalizations of the Holton-McKay minimum-cardinality counterexamples are also contained in the family.

Significance. If the explicit attachment rules, base cases, and inductive arguments hold, the work supplies a unifying recursive framework for both hamiltonian and non-hamiltonian planar cubic graphs. The self-contained exhaustive case analysis on paths through the three connection vertices of each fragment, together with direct verification that no smaller family member is non-hamiltonian, constitutes a verifiable combinatorial contribution that embeds known counterexamples without external results beyond standard facts on cubic graphs.

minor comments (3)

[§3] The recursive definition of the family (likely in §3) would benefit from an explicit statement of the three possible attachment configurations at the connection vertices to make the inductive step easier to follow.
[§4] A small table or diagram summarizing the orders and hamiltonicity status of the first few members of the family (base case through two or three iterations) would clarify the minimality claim.
Notation for the connection vertices (e.g., a, b, c) is introduced but occasionally reused without re-labeling in later figures; consistent labeling across diagrams would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation for minor revision. The referee's summary accurately reflects the manuscript's contributions regarding the recursive construction of an infinite family of planar cubic graphs.

read point-by-point responses

Referee: The manuscript constructs an infinite family of planar cubic graphs by recursively combining prisms with Tutte fragments. It positions Tutte's counterexample to Tait's conjecture as a minimal non-hamiltonian element within this family (in a specified sense) and shows that generalizations of the Holton-McKay minimum-cardinality counterexamples are also contained in the family.

Authors: We appreciate the referee's accurate summary. The paper indeed defines the family via recursive attachment of prisms to Tutte fragments, establishes minimality of Tutte's graph via exhaustive case analysis on paths through the three connection vertices, and verifies that no smaller member is non-hamiltonian while containing the Holton-McKay generalizations as specific cases. revision: no

Circularity Check

0 steps flagged

No significant circularity; explicit constructive family with inductive verification

full rationale

The paper's central claim is an explicit recursive construction that combines prism graphs with Tutte fragments to generate an infinite family of planar cubic graphs, positioning Tutte's counterexample as a minimal non-Hamiltonian element while also containing generalizations of Holton-McKay examples. The derivation proceeds via base cases, attachment rules at three connection vertices, and inductive arguments that preserve Hamiltonicity or non-Hamiltonicity through exhaustive path analysis. These steps are self-contained combinatorial arguments that do not invoke fitted parameters, self-definitional quantities, or load-bearing self-citations whose validity depends on the present result. No equation or claim reduces by construction to prior inputs; the minimality and family membership are established directly by the construction and case checks rather than by renaming or smuggling an ansatz.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim depends on standard definitions and closure properties of planar cubic graphs, prisms, and Tutte fragments under the described operations; these are treated as background from graph theory rather than newly invented here.

axioms (1)

standard math Standard definitions and basic properties of planar cubic bridgeless graphs, Hamiltonian cycles, and 3-edge-colorings hold as in classical graph theory.
The abstract invokes these concepts without re-deriving them.

pith-pipeline@v0.9.0 · 5595 in / 1385 out tokens · 41865 ms · 2026-05-18T08:37:35.375247+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Using the graphs of prisms and Tutte Fragments, we construct an infinite family of hamiltonian and non-hamiltonian graphs in which Tutte’s counterexample to Tait’s conjecture appears in a certain sense as a minimal element.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.