The following occurred to me while playing [Sokoban](https://en.wikipedia.org/wiki/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?



Push function on simple undirected graphs
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).


