# Are all cubic graphs almost Hamiltonian?

Call a graph $$G$$ $$n$$-almost-Hamiltonian if there is a closed walk in $$G$$ that visits every vertex of $$G$$ exactly $$n$$-times. So a Hamiltonian graph is $$n$$-almost-Hamiltonian for all $$n$$. Are all cubic graphs $$n$$-almost-Hamiltonian for some sufficiently large $$n$$?

• Your answer makes clear that every connected graph is $n$-almost Hamiltonian for all even $n$. Is there a chance that some graphs, such as all cubic graphs, are $n$-almost Hamiltonian for some odd $n$? – Menachem Feb 4 '19 at 8:02
• @Menachem I gave the example $n=3$. Also note that my proof only works easily for regular graphs. Many graphs, for example an unbalanced bipartite graph, are not $n$-almost Hamiltonian for any $n$. – Brendan McKay Feb 4 '19 at 9:15