Push function on simple undirected graphs

Question

The following occurred to me while playing Sokoban.

Let $G=(V,E)$ be a finite, simple, undirected, and connected graph with $|V|>1$. We call a function $f:V\to V$ a push function if $\{x,f(x)\}\in E$ for all $x\in V$. (Note that a push function cannot have fixed points, and that the composition of two push functions is usually not a push function.)

We say that $G$ is contractible if there is $n\in \mathbb{N}$ and there are push functions $f_1,\ldots,f_n:V\to V$ such that $$\text{im}(f_n\circ \ldots \circ f_1) = \{v\} \text{ for some } v\in V.$$

I think I have been able to prove that if a connected graph $G$ with more than 1 vertex is contractible then $G$ contains an odd cycle. Does the converse hold?

Answer 1

Yes. If you have an odd cycle, then you can reduce the size of the image by first pushing two different vertices of the current image to the cycle, and then push them to the same vertex. So a graph is contractible if and only if it is connected and not bipartite (or has only one vertex).