A Tight Lower Bound for Cycle Detection in Grid Graphs

We prove that any algorithm for detecting cycles in an $m\times n$ grid graph, where cells are colored and adjacency is defined by matching colors, must read all $mn$ cells in the worst case for all grids with $m\ge 2$ and $n\ge 2$. The proof is by adversary argument: we construct an adaptive adversary that maintains ambiguity – one completion containing a cycle and one without – until the final cell is read. The construction proceeds by tiling the grid with $2\times 2$, $2\times 3$, $3\times 2$, and $3\times 3$ blocks, each equipped with an independent block adversary, composed via a checkerboard isolation scheme.