Cat vs Mouse (bipartite graphs) - can mouse evade capture?

[KOSS]

On a bipartite graph a game of cat vs mouse can be played, with say both the cat and mouse starting on a "red" vertex. We colour the vertices so that no two of the same colour are connected by an edge (can always be done with a bipartite graph of course). The game is played by cat and mouse moving to adjacent vertices in turn. If the cat moves first we thus know it cannot "win" by landing on the mouse, a fact soon discovered by a child.

Here are my questions (and apologies if they have been answered elsewhere): if the mouse must move first, then the cat has a chance, since on each turn it will then always be moving to a vertex the same color as the mouse. But on a finite graph, does this always guarantee a win for the cat, i.e., can the cat always corner the mouse? Or are there some graphs (which ones?) where the mouse can run around without ever being cornered? And if not, then (given the graph) is there a decision procedure for the minimum number of moves it takes for the cat to win in such circumstances?

 

[Tinyboss]

Jerry can elude Tom forever on a cyclic graph.

Cyclic graphs with an even number of vertices are bipartite.

Edit: In fact, bipartite or not, I think it just comes down to whether the graph has a cycle (and whether the mouse can reach it from the starting configuration).

 

[KOSS]

Yeah, I get that, thanks. I'm still figuring out how to prove these things...