Lovász conjecture
Statement
Call a finite simple graph vertex-transitive if its automorphism group acts transitively on , and call a cycle in Hamiltonian if it passes through every vertex of exactly once.
For a cubic graph (every vertex of degree ), let denote the triangle replacement of : the vertex set of is the set of pairs with , and an endpoint of ; two such pairs and are adjacent in if either and (so the three pairs at each vertex of form a triangle), or and .
Let be the Petersen graph, i.e. the graph whose vertices are the -element subsets of , two such subsets being adjacent when they are disjoint.
Let be the Coxeter graph, i.e. the graph on the vertices
with edges , , , and , , for all .
Then every finite connected vertex-transitive graph contains a Hamiltonian cycle, with the exception of exactly five graphs up to isomorphism, namely
each of which is finite, connected and vertex-transitive, contains a Hamiltonian path, and contains no Hamiltonian cycle.
Record
- Added
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.