Chvátal's toughness conjecture
Statement
For a finite simple graph and a set , let denote the number of connected components of the graph obtained from by deleting . For a real number , call -tough if for every integer and every with one has ; equivalently, is -tough if
(Under this convention every complete graph is -tough for every , since deleting vertices never leaves more than one component.) A graph on vertices is Hamiltonian if it contains a cycle passing through each of its vertices exactly once.
There exists a real number such that every -tough graph on at least vertices is Hamiltonian.
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.