Claro, comprobar que es de Hamilton implica probar todos los caminos posibles y si uno es de Hamilton pues sacas la matriz de adyacencia de dicho camino.
Aquí te deja una explicación muy buena (eso sí, está en inglés) de cómo implementar la matriz de adyacencia de tu grafo hamiltoniano.
http://www.geeksforgeeks.org/backtra...ltonian-cycle/