Suppose we play the following game. We place a bunch of hexagonal game board tiles on a table, edge-to-edge, to form our playing field. On the field, we place two game pieces, a cop (blue) and a robber (red). The cop and robber take turns, either moving to an adjacent hex or passing (staying put). The cop wins if he can end a turn on the same hex as the robber. The robber wins by evading the cop forever. Who has the advantage?

It turns out to depend on what game board shapes are allowed. If the hexes of the board can completely surround a hole (a shape where one or more hexes could have been placed, but weren't) then the robber can win by keeping the hole between himself and the robber. But if there are no holes, then the cop always wins.

Probably there is a direct strategy that shows this, but it's also possible to prove that the cop wins by using the theory of

cop-win graphs, graphs in which the cop wins a generalized version of this game, with the players moving on the vertices of a graph rather than the hexes of a game board. Cop-win graphs are the same as dismantlable graphs, the graphs that can be reduced to a single vertex by repeatedly removing a vertex whose closed neighborhood is a subset of another vertex's closed neighborhood. And the adjacency graphs of systems of hexes with no holes are always dismantlable.

To see this, consider the tree of 2-vertex-connected components of the adjacency graph of the hexes. For instance, the example above has five 2-connected components: the hexagonal shape formed by the seven hexes in the lower left, a big mass of 18 hexes in the center and right, and three single-hex components in the upper left. (Two of these single hexes are connected to the rest of the board only by a single edge; the other single-hex component lies between the two big components.) Choose arbitrarily a single leaf component of this tree (the 18-vertex component, or the two single-hex components connected to the rest by a single edge). If this component is a single hex, then its closed neighborhood is a two-hex set, consisting of itself and its one neighbor. In this case, its neighborhood is always a subset of its neighbor's component.

Otherwise, if the leaf component that you picked is a nontrivial 2-connected component, such as the 18-vertex component of the example, walk counterclockwise around its boundary. The angles that you turn always have to add up to 2pi, so you must have passed at least three points where your walk turns counterclockwise by an angle of pi/3 (a boundary hex adjacent to two others, such as the starting point of the cop in the example) or 2pi/3 (a boundary hex adjacent to three others). In particular, one of these three hexes is not the one that connects your component to the rest of the game board. If it has two neighbors, its neighborhood is a subset of either of its neighbors' neighborhoods. And if it has three neighbors, its neighborhood is a subset of its middle neighbor's neighborhood. So either way, we can find a hex to remove. By repeating this process, we can show that the adjacency graph of the hexes is always dismantlable. More strongly, it's dismantlable with any distinguished vertex (such as the cop's starting location) as its final vertex.

Unfortunately, I don't know of a simple explicit strategy for the cop, even on a polyhex board rather than a general graph. The cop's strategy in the publications on this subject is: remove a removable vertex, and then follow the optimal strategy (recursively) for the remaining graph, pretending that the robber is on the parent of the removed vertex whenever it is actually on the removed vertex. Then, when you think you've won according to this strategy, you will either have actually won, or achieved a position where the robber is on the removed vertex and you're on its parent (where you're pretending that the robber is). But in this case, you can win in one more move.

One way to visualize this strategy is to draw a tree representing the parent of each removed vertex, together with numbers indicating the order in which the vertices were removed:

Then, at each turn, add back one more vertex (in the reverse of the order that they were removed) and move to the lowest-numbered ancestor of the robber's current position among the ones that have been added back so far. For instance, in the position shown, to figure out what to do on your first move, you would add back hex 28, realize that the lowest-numbered ancestor of the robber's position is hex 29 (the one you're already on), and pass. After the robber moves, you would add back hex 27, and (since all moves for the robber land in the subtree of hex 27) move there. Etc.

But this strategy involves keeping track of a spanning tree, a numbering, and a current set of added-back tiles. Maybe for the hex board there's a simpler strategy based only on your position and the position of the robber?

And finally, what about other kinds of game tiles? Square tiles don't work with edge-to-edge adjacency: the robber can evade the cop by staying on the opposite side of a 4-cycle. But for squares with corner adjacency (and no holes) the cop can always win; for instance, consider cops and robbers that move like kings on a chessboard. Being planar with only three game tiles meeting at a corner isn't good enough for the cop to win: the robber always wins on a dodecahedron by staying as far as possible from the cop. Maybe some other polyforms than polyhexes will also allow the cop to always win.