2025/10/02 by Sawczuk, Hamilton, Gnang, Edinah
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.02473
The Hamiltonian cycle polynomial can be evaluated to count the number of Hamiltonian cycles in a graph. It can also be viewed as a list of all spanning cycles of length n. We adopt the latter perspective and present a pair of original proofs for the Hamiltonian cycle identity which relates the Hamiltonian cycle polynomial to the important determinant and permanent polynomials. The first proof is a more accessible combinatorial argument. The second proof relies on viewing polynomials as both linear algebraic and combinatorial objects whose monomials form lists of graphs. Finally, a similar identity is derived for the Hamiltonian path polynomial.