Question

State true or false:

Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.

(a) Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.

(b) true

(c) false

The question was posed to me in an internship interview.

My doubt is from Node-Cover Problem, Hamilton Circuit Problem in portion Intractable Problems of Automata Theory

Answer 1

Right option is (a) Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.

The best explanation: Handshaking lemma states that ‘Every finite undirected graph has an even number of vertices  with odd degree.