I have the below algorithm that appears to find a Hamiltonian path in undirected graphs (if one exists). I've tested with every graph I could find or come up with and it appears to work. I've included an example of it working on a decision problem graph.
I'm trying to find a counter example graph and am hoping someone here could provide one?
- Draw the graph, $G$, such that $\forall N \in G, N$ shares the exterior region surrounding $G$
- Greedy number the graph regions, $R$, formed by the regions enclosed by edges of G, R = 1,2,3....,m-1 and label the exterior region m
- Label each $N \in G$ as the ordered set of the joint of all number-labeled regions of G and the exterior number m that confluences at each node. Consider the number formed by the joint of the digits of each ordered set for each node, $C_{N}$. That is, $\forall N \in G,$ $C_N = (\bigcap_{i \subseteq \mathbf{I}}^{}R_{i} \oplus m ) $
- Begin at a random point.
- Connect to the nearest $C_N$ such that the nearest $C_N$ compared to the current $C_N$ is the smallest linked (shares an edge) number to the current $C_N$ yet to be connected. Move to that connected number.
- Repeat step 5 across $G$ until either all $C_N$ have been connected or step-5 cannot continue.
- Check both ends of the path made cannot continue as per steps 5-6.
- If the other end of the path can continue as per steps 5-6 then repeat from 5 beginning from the path's other end until all nodes are connected at least once.
- If all nodes can be connected in a path then there is a connected path, otherwise there is not a connected path.
