3 ms·
How can a Hamiltonian cycle be increasing? If you have one and you add an edge, then you no longer have a chain of edges that passes through every vertex exactl
by leephillips 5y ago
How can a Hamiltonian cycle be increasing? If you have one and you add an edge, then you no longer have a chain of edges that passes through every vertex exactly once, because two vertices will have two edges.
- omnicognate 5y agoThe chain of edges forming the cycle doesn't have to include all edges in the graph. There just has to exist a set of edges that form a Hamiltonian cycle. Adding further edges doesn't change that (but adding further vertices would). Edit: Put another way, it's not the Hamiltonian cycle itself that's increasing, it's the property of there existing a Hamiltonian cycle in the graph.
- leephillips 5y agoSo the definition in the article, “a chain of edges that passes through every vertex exactly once”, is incorrect?
- omnicognate 5y agoNo, that's the correct definition of a Hamiltonian cycle. However, the article isn't as clear as it could be about what the "increasingness" aspect applies to. > It’s possible to think about any property, so long as it is “increasing” — that is, if adding more edges to a graph that already contains the property will not destroy the property. The "property" here isn't the Hamiltonian cycle itself, it's the property "a Hamiltonian cycle exists within this graph". This property, rather than the cycle itself, is increasing: if you add edges to a graph that contains a Hamiltonian cycle it will still contain a Hamiltonian cycle.
- deleted 5y ago[deleted]
- leephillips 5y agoAh, I get it now. Thanks.