ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a finite undirected graph with the following four properties:

GG is planar: it can be embedded in the Euclidean plane with no two edges crossing. 2. GG is 33-vertex-connected: GG has at least 44 vertices and, for every set SS of at most two vertices, the graph G−SG - S obtained by deleting SS and all incident edges is connected. (A planar 33-connected graph is called polyhedral.) 3. GG is bipartite: its vertex set admits a partition into two classes such that every edge of GG has one endpoint in each class. 4. GG is cubic (33-regular): every vertex of GG is an endpoint of exactly three edges.

Then GG is Hamiltonian, i.e. GG contains a cycle passing through each of its vertices exactly once.

Equivalently, in the language of polytopes: if PP is a simple 33-dimensional convex polytope (every vertex of PP lies on exactly three edges) such that every face of PP has an even number of edges, then the graph formed by the vertices and edges of PP has a Hamiltonian cycle.

Record

Added
Links

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.