Call a graph $G$ $n$almostHamiltonian if there is a closed walk in $G$ that visits every vertex of $G$ exactly $n$times. So a Hamiltonian graph is $n$almostHamiltonian for all $n$. Are all cubic graphs $n$almostHamiltonian for some sufficiently large $n$?
1 Answer
Yes, every connected cubic graph is 3almostHamiltonian. Replace each edge by two parallel edges then follow an Eulerian circuit.
In the case of a bridgeless cubic graph, you can add a perfect matching instead of doubling each edge, which shows they are 2almostHamiltonian.

$\begingroup$ 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$? $\endgroup$– MenachemFeb 4, 2019 at 8:02

5$\begingroup$ @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$. $\endgroup$ Feb 4, 2019 at 9:15