20190513, 09:33  #1 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 
Hamiltonian path
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': Code:
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 
20190513, 10:06  #2  
May 2019
2^{2} Posts 
Quote:
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. Last fiddled with by henryzz on 20190513 at 11:00 

20190513, 10:34  #3 
May 2019
2^{2} Posts 
Tackle by parity, 13 white / 12 black. You start from black have to visit 13 white interspersed with 11 black. Not possible,
Last fiddled with by henryzz on 20190513 at 10:59 
20190513, 10:59  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·1,951 Posts 
@AKG Doesn't that only apply to cycles not paths?
I have added spoilers so that others can solve. 
20190513, 12:12  #5 
May 2019
2^{2} Posts 
That is condition, pass through 'x' only once. Answer is not concerned with which path or cycle you follow.

20190514, 01:54  #6 
Romulan Interpreter
Jun 2011
Thailand
17×19×29 Posts 
This problem is similar to the DominoChess 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... Last fiddled with by LaurV on 20190514 at 02:04 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The Fastest Path  a1call  Puzzles  23  20160323 17:46 
Path Counting  henryzz  Puzzles  13  20140917 11:21 
Best settings and upgrade path for i72600  emily  Hardware  20  20120302 08:45 
Expected Path Length  davar55  Puzzles  12  20080226 21:53 
Are you in the path of Isabel  jocelynl  Soap Box  14  20030922 20:38 