Torsten Sillke, 20.06.97 The Hamiltonian paths of a special graph are searched in: Frits G"obel, Solving a Pentomino Problem with Graph Theory, CFF 43, (1997), p4-5 I dislike the drawing of the given graph. First I cut of the lose ends. It remains a 8 vertex graph and we are looking for Hamiltonian path from F to Y. If I discard Y, I am looking for a path from F to a vertex in {N,P,T}. At last I reduce: X X | / \ A to / \ / \ / \ X X X-------X for A in {V,W,Z}. Multiple edges can be discarded, as at most one can be used without double visiting a vertex. It remains a K_4 with the vertices {F,N,P,T}. Now there are 6 = 3! Hamiltonian pathes starting at F: F---N---P---T F---N---T---P F---P---N---T F---P---T---N F---T---N---P F---T---P---N Now try to extend each path by inserting the vertices {V,W,Z} into the three edges (and add Y). This need not be possible, but in this case each reduced solution extends uniquely (unique matching). F-Z-N-W-P-V-T-Y F-W-N-Z-T-V-P-Y F-W-P-V-N-Z-T-Y F-W-P-V-T-Z-N-Y F-Z-T-V-N-W-P-Y F-Z-T-V-P-W-N-Y Now connect the lose ends to get all solutions: X-F-Z-N-W-P-V-T-Y-U-L-I X-F-W-N-Z-T-V-P-Y-U-L-I X-F-W-P-V-N-Z-T-Y-U-L-I X-F-W-P-V-T-Z-N-Y-U-L-I X-F-Z-T-V-N-W-P-Y-U-L-I X-F-Z-T-V-P-W-N-Y-U-L-I 2nd approach: ------------- The alternation between vertices from {F,N,P,T} and {V,W,Y,Z} is easily seen, as {V,W,Y,Z} is an independent set. Therefore a Hamiltonian path between F and Y must be alternating. So wie can discard all edges between vertices from {F,N,P,T}. After ommitting Y the resulting graph is very sparse: F / \ Z W / \ / \ T N P \ | / \ | / \|/ V All Hamiltonian pathes starting at F end in {N,P,T} and therefore at Y. Again we find 6 pathes.