Hamiltonian path

[lukerichards]

Hi,

One of my students gave me this problem this morning. I know very little about graph theory to know if it's possible. I'm enjoying puzzling through it at the moment so any solutions of proofs of impossibility, please cover with spoiler tags!

Find a hamiltonian path* through the following network which starts at the point 'O':

x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - O - x

*must pass through every vertex ('x') exactly once.

[AKG]

Originally Posted by lukerichards

Hi,

One of my students gave me this problem this morning. I know very little about graph theory to know if it's possible. I'm enjoying puzzling through it at the moment so any solutions of proofs of impossibility, please cover with spoiler tags!

Find a hamiltonian path* through the following network which starts at the point 'O':

x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - O - x

*must pass through every vertex ('x') exactly once.

you need parity argument.

Mark each x black and white like a a chessBoard (corner white preferably).
You have to start from a black square (total count 12), visit 13 white square and 11 black which is impossible.

[AKG]

Tackle by parity, 13 white / 12 black. You start from black have to visit 13 white interspersed with 11 black. Not possible,

[henryzz]

@AKG Doesn't that only apply to cycles not paths?

I have added spoilers so that others can solve.

[AKG]

That is condition, pass through 'x' only once. Answer is not concerned with which path or cycle you follow.

[LaurV]

This problem is similar to the Domino-Chess puzzle, which sucked tons of ink a century ago... All ladies from higher society used at a point in their life, at some party, to play placing dominoes on the chess board. Even nowadays, if you propose it as a social game at some party, plenty of people will argue for hours about placing dominoes on this or that direction. Try it! (be prepared with a chess board and a domino set hehe).

Solving such problems by backtrack (the natural way the human mind thinks) has exponential complexity. For just a little bigger board you will need thousands of years. Unless you see the parity trick. (Yeah, I read the spoilers above, but I knew the problem and the solution long before, Graph Theory was one of my strongest points in school, we - as a group of about 10 students - and our professor did few important steps in proving the infamous (at the time) Berge's conjecture (now it is known as the "strong perfect graph theorem"). Which, I believe, it is an important step in proving that P=NP. No joke, talk to you about this in about 50 years...