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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**