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 - The Fusion of Science and Community**

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?

Loading...

Similar Threads - Mouse bipartite graphs | Date |
---|---|

Cyclic Graph Proof? | Jan 3, 2015 |

Graphing Covariant Spherical Coordinates | Jan 6, 2013 |

Equation to graph a 180 degree curve comprised of a radius and an ellipse | Nov 30, 2012 |

Interpretation on the meaning of some graph theory statements | Nov 11, 2012 |

**Physics Forums - The Fusion of Science and Community**