Hamiltonian cycle concept
E455347
The Hamiltonian cycle concept is a fundamental idea in graph theory describing a cycle that visits each vertex of a graph exactly once and returns to the starting point.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Hamiltonian cycle concept canonical | 1 |
| Hamiltonian path problem | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T4585391 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Hamiltonian cycle concept Context triple: [William Rowan Hamilton, knownFor, Hamiltonian cycle concept]
-
A.
Seven Bridges of Königsberg problem
The Seven Bridges of Königsberg problem is a historic puzzle in graph theory that asks whether one can walk through the city of Königsberg crossing each of its seven bridges exactly once, leading Euler to found the field of topology.
-
B.
Conway's 99-graph problem
Conway's 99-graph problem is an unsolved combinatorial question in graph theory, posed by John H. Conway, concerning the existence and properties of a hypothetical 99-vertex graph with highly constrained adjacency conditions.
-
C.
Conway's thrackle conjecture
Conway's thrackle conjecture is an unsolved problem in combinatorial geometry asserting that in any drawing of a graph where every pair of edges meets exactly once, the number of edges cannot exceed the number of vertices.
-
D.
Conway circle theorem
The Conway circle theorem is a geometric result in triangle geometry that identifies a special circle associated with a triangle and certain constructed points, revealing notable collinearities and concyclicity relationships.
-
E.
de Bruijn sequence
A de Bruijn sequence is a cyclic sequence over a given alphabet in which every possible subsequence of a fixed length appears exactly once.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Hamiltonian cycle concept Target entity description: The Hamiltonian cycle concept is a fundamental idea in graph theory describing a cycle that visits each vertex of a graph exactly once and returns to the starting point.
-
A.
Seven Bridges of Königsberg problem
The Seven Bridges of Königsberg problem is a historic puzzle in graph theory that asks whether one can walk through the city of Königsberg crossing each of its seven bridges exactly once, leading Euler to found the field of topology.
-
B.
Conway's 99-graph problem
Conway's 99-graph problem is an unsolved combinatorial question in graph theory, posed by John H. Conway, concerning the existence and properties of a hypothetical 99-vertex graph with highly constrained adjacency conditions.
-
C.
Conway's thrackle conjecture
Conway's thrackle conjecture is an unsolved problem in combinatorial geometry asserting that in any drawing of a graph where every pair of edges meets exactly once, the number of edges cannot exceed the number of vertices.
-
D.
Conway circle theorem
The Conway circle theorem is a geometric result in triangle geometry that identifies a special circle associated with a triangle and certain constructed points, revealing notable collinearities and concyclicity relationships.
-
E.
de Bruijn sequence
A de Bruijn sequence is a cyclic sequence over a given alphabet in which every possible subsequence of a fixed length appears exactly once.
- F. None of above. chosen
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
cycle in a graph
ⓘ
decision problem ⓘ graph theory concept ⓘ |
| alsoCalled |
Hamiltonian circuit
ⓘ
Hamiltonian tour ⓘ |
| appearsIn |
network design
ⓘ
polyhedral combinatorics ⓘ routing problems ⓘ |
| appliesTo |
directed graphs
ⓘ
undirected graphs ⓘ |
| asks | whether a given graph contains a Hamiltonian cycle ⓘ |
| complexityClass | NP-complete ⓘ |
| complexityOfRecognition | NP-complete in general graphs ⓘ |
| contrastedWith | Eulerian cycle NERFINISHED ⓘ |
| decisionProblem | Hamiltonian cycle problem ⓘ |
| definition | a cycle in a graph that visits each vertex exactly once and returns to the starting vertex ⓘ |
| edgeConstraint | uses only edges of the graph ⓘ |
| exampleGraphWith | complete graph Kn for n ≥ 3 ⓘ |
| exampleGraphWithout |
star graph Kn,1 for n ≥ 2
ⓘ
tree with more than two vertices ⓘ |
| existsIn | Hamiltonian graph ⓘ |
| field | graph theory ⓘ |
| generalizedTo | infinite graphs with appropriate definitions ⓘ |
| historicalOrigin | Icosian game of William Rowan Hamilton NERFINISHED ⓘ |
| isSubgraphOf | underlying graph ⓘ |
| length | number of vertices in the graph ⓘ |
| namedAfter | William Rowan Hamilton NERFINISHED ⓘ |
| property | spans all vertices of the graph ⓘ |
| relatedConcept |
Eulerian cycle
ⓘ
Hamiltonian path NERFINISHED ⓘ |
| representation | sequence of vertices forming a simple cycle ⓘ |
| requires |
finite graph in standard definition
ⓘ
graph to be connected for existence ⓘ |
| returnsTo | starting vertex ⓘ |
| specialCaseOf | cycle ⓘ |
| studiedIn |
algorithmic graph theory
ⓘ
extremal graph theory ⓘ |
| sufficientCondition |
Bondy–Chvátal theorem
NERFINISHED
ⓘ
Chvátal–Erdős theorem NERFINISHED ⓘ Dirac's theorem NERFINISHED ⓘ Ore's theorem NERFINISHED ⓘ |
| tractableOn |
graphs of bounded treewidth
ⓘ
tournaments ⓘ |
| usedIn |
combinatorial optimization
ⓘ
computational complexity theory NERFINISHED ⓘ traveling salesman problem NERFINISHED ⓘ |
| vertexConstraint | includes every vertex of the graph ⓘ |
| visitsEachVertex | exactly once ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Hamiltonian cycle concept Description of subject: The Hamiltonian cycle concept is a fundamental idea in graph theory describing a cycle that visits each vertex of a graph exactly once and returns to the starting point.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Hamiltonian path problem