Let $G=(V,E)$ be a connected simple undirected graph. A *way* in $G$ is a function $w:\{1,\ldots, n\}\to V(G)$ for some positive integer $n$, such that $\text{im}(w) = V(G)$, and for all $k\in \{1,\ldots, n-1\}$ we have $\{w(k), w(k+1)\} \in E$.


We define the *hamiltonicity* of $G$ by $$H(G) = \min\{n\in\mathbb{N}:\text{ there is a way } w:\{1, \ldots n\}\to V(G)\} - |V(G)|.$$


(A connected graph is Hamiltonian if and only if $H(G) = 0$.)


Is it true that for all connected graphs we have $H(G) \leq |V(G)| - 1$? Or can $H(G)$ become larger, even arbitrarily large with respect to $|V(G)|$?



"Hamiltonicity" of a graph
$H(G)\leq \lvert V(G)\rvert-1$ for every finite connected graph. 


Proof. Consider any spanning tree $T$ of $G$, double every edge of $T$, choose any Euler tour $W$ of this auxiliary graph, consider the projection $\mathrm{p}(W)$ of $W$ to $G$. Then $\mathrm{p}(W)$ is a way in your sense having a domain of $2\lvert V(G)\rvert-1$ elements. After subtracting $\lvert V(G)\rvert$ we obtain the required upper bound of $\lvert V(G)\rvert-1$ on the "hamiltonicity" (in your sense).


