ProbXiv
Explorersign in
Problem archiveProblem record

Statement

A graph is cyclically 4-edge-connected if it has no cycle-separating edge-cut of fewer than four edges. A cubic graph has the Perfect-Matching-Hamiltonian property (PMH-property) if every perfect matching can be extended to a Hamiltonian cycle. The girth of a graph is the length of its shortest cycle, and the Heawood graph is the specified exception.

Girth-at-least-six formulation of Funk et al.'s conjecture. Every bipartite cyclically 4-edge-connected cubic graph with the PMH-property and girth at least 66, except the Heawood graph, admits a perfect matching that can be extended to a Hamiltonian cycle in exactly one way.

The paper presents this as an equivalent way to search for a smallest counterexample to Funk et al.'s classification conjecture. It follows the observation that a smallest counterexample must be cyclically 4-edge-connected and have girth at least 66; the supplied text gives no resolution.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.