William Hamilton has an interesting variation of Euler's Seven Bridges puzzle [0] which asks whether there is a path visiting every vertex of a polyhedron exact

William Hamilton has an interesting variation of Euler's Seven Bridges puzzle [0] which asks whether there is a path visiting every vertex of a polyhedron exactly once. Strangely, while the complexity of detecting Eulerian paths is linear in the number of edges [1], the complexity of detecting Hamiltonian paths is NP-complete [2]! Hamilton (who was also fond of crossing bridges [3]) developed some interesting algebraic structures to study the polyhedron problem [4]. I recently became interested in Eulerian and Hamiltonian paths after taking a class in Graph Representation Learning [5]. In it, I learned there are many interesting connections between algebra and graph theory [6] and started writing a library called Kaliningraph to study some of those connections [7]. [0]: http://eulerarchive.maa.org/docs/originals/E053.pdf http://eulerarchive.maa.org/docs/originals/E053.pdf [1]: https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_alg... [2]: https://en.wikipedia.org/wiki/Hamiltonian_path https://en.wikipedia.org/wiki/Hamiltonian_path [3]: https://en.wikipedia.org/wiki/Broom_Bridge https://en.wikipedia.org/wiki/Broom_Bridge [4]: http://www.kurims.kyoto-u.ac.jp/EMIS/classics/Hamilton/PRIAIcos.pdf http://www.kurims.kyoto-u.ac.jp/EMIS/classics/Hamilton/PRIAI... [5]: https://cs.mcgill.ca/~wlh/comp766/ https://cs.mcgill.ca/~wlh/comp766/ [6]: https://www.cs.yale.edu/homes/spielman/sagt/sagt.pdf https://www.cs.yale.edu/homes/spielman/sagt/sagt.pdf [7]: https://github.com/breandan/kaliningraph https://github.com/breandan/kaliningraph