CODEWITHSUNDEEP
hamiltonian-cyclehamiltonian-path
Versteher
Versteher

Reputation: 23

On example where no Hamilton path is possible to make Hamilton cycle

https://www.youtube.com/watch?v=3xeYcRYccro&list=PLoJC20gNfC2gmT_5WgwYwGMvgCjYVsIQg&index=32

12:10 states that that example is a Hamilton path. This is an example to shew that a Hamilton path cannot make a Hamilton graph. Indeed all verteces are covered by the red line. A Hamilton path is that touches all verteces once. Satisfied. If we add an edge from right upper to right lower, won't we have a Hamilton cycle. We can then start at one vertex, run all other 3 and finish at the beginning. Once. Why not a Hamilton cycle.

Upvotes: -2

Views: 288

Answers (1)

Federico Andreoli
Federico Andreoli

Reputation: 465

Look carefully at the question. It says: "Can a hamilton path ALWAYS be used to form an ham-cycle?"

So if you find only one example that has an ham-path but not an ham-cycle the answer is no.

The graph you're suggesting (upper and lower right vertices connected) surely has both path and cycle, but it does not answer to the question.

The other important thing is that removing an arch is different from adding one. You can see that taking a subset of a cycle is basically taking "almost the same object"; when you instead add an arch you create a new instance, a new graph that is different from the other. It's quite difficult to understand...

Upvotes: 0

Related Questions