1-7. The Round Table or the People Invited to the Grand Finale

Finally, we obtained the Hamiltonian path. If there exists a branch conjoining the end point and the start point, a Hamiltonian tie is completed and the experimentation ends. However, for instance, a complete graph has a number of N! of different Hamiltonian paths. Moreover, we already have warped with the re-experimental graph method! Although we had reached to the place, yet should all of those come to nothing like a bubble? No, it is not so. We, who have advanced the experiments never retrograding, have arrived in the final stage of this drama. Well, let us introduce to you the people who are invited to the grand finale of the stage.*

Firstly enter a Hamiltonian path obtained with the short-circuit / re-experimental graph method and a remainder branches set obtained by removing the path from graph G. If the remainder branches set is large enough, it might be possible to get one more Hamiltonian path from the branch-section graph of this branches set. Repeating this operation, we cut out a maximal Hamiltonian paths set of and let the rest as remainder branches set. Hamiltonian paths have not common branches and the branches sethas not a branch conjoining end point and start point of these paths.

One Hamiltonian path includes N-1 branches. It is probable that we cut off such Hamiltonian path at most in N/2, and we can line up every branches of these Hamiltonian paths in a matrix of N rows * N/2 columns. One column comprises branches included in a Hamiltonian path, branches standing in a row are arranged and indexed with the points appear in the left end Hamiltonian path. If the remainder branches set is not empty, at least one column remains, so the last column is assigned to the remainder branches set.

On the panel of the matrix buttons are arranged, on a button pasted a label showing the symbol of the end point of the branch. In each column, there is a button with label entered nothing and the labels of the other buttons are entered every different symbols. And also labels on buttons of each rows have every different symbols. Push a button, then a lamp housed in the button is lighted, and when we succeed in lighting those N lamps of every different labels, a big lamp in front of the panel shall be lighted and a fanfare will be played up.

Gradually, all guests have come in and it seems the game begin surrounding a big panel on the Round Table. For the beginning, push every buttons of the first column and light their lamps. There is one button not to be lighted, so find another button in the same row and light it's lamp. Yet, pushing this button, a lamp with the same symbol of the button fades away with flickering effect like a candle dying out. At every time, a big stir with a sigh resounds, by and by the game comes into exciting and glowing. Now, shall this game really come to the end toward daylight? What we search, "a method to control one's fortune proved mathematically", has finally been found?

* It was proven that both Hamiltonian Path Problem and Hamiltonian Circuit Problem are NP-complete. For example see Garey & Johnson [GJ]. If you have a polynomial time algorithm for Hamiltonian Circuit Problem, then you can solve Path version by adding a vertex u to G and connect every vertices in G with u. If the derived graph has a Hamiltonian cycle, then G has a Hamiltonian Path. For the opposite direction, try this. For all edges (i,j) in G, add a vertex k and separate the edge into (i,k) and (k,j). Then if the derived graph has a Hamiltonian path, then one of the end vertices of the path must be an added vertex k and you can certify that G has a Hamiltonian Circuit. Consequently if we had established a way to find a Hamiltonian Path, then the whole of the problem was already solved.