← All papers
First page of The cop number of the flower snarks, and the generalized Petersen graphs with cop number two

The cop number of the flower snarks, and the generalized Petersen graphs with cop number two

Aarav Ghai

math.CO Nov 12, 2026 · v1
Formalizes in Lean 4 with Mathlib that the flower snark cop number is 3 for n≥5, and lower bounds for generalized Petersen graphs.
We study two questions of Morris, Runte and Skelton (Australas. J. Combin. 83 (2022)) on the game of Cops and Robbers. First, we show that the flower snark $J_n$ has cop number $3$ for every $n\geq 5$, and that $J_3$ has cop number $2$. The upper bound comes from a three-cop strategy, which we call the rolling wall. It works on every connected graph whose vertices can be arranged in a cycle of columns, each dominated by a single vertex. Because only one cop moves on each turn, the same strategy also shows that the lazy cop number of $J_n$ is $3$ for $n\geq 5$. Second, we prove the conjecture of Morris, Runte and Skelton that the only generalized Petersen graphs with cop number $2$ are $\mathrm{GP}(n,1)$ and the four graphs $\mathrm{GP}(6,2)$, $\mathrm{GP}(8,2)$, $\mathrm{GP}(9,3)$ and $\mathrm{GP}(12,3)$. The new ingredient is an explicit robber strategy showing that two cops do not suffice on $\mathrm{GP}(3k,k)$ and $\mathrm{GP}(4k,k)$ for $k\geq 4$. The theorem on flower snarks and all of the new lower bounds have been formally verified in the Lean 4 proof assistant.

Morris, Runte and Skelton asked for the cop number of the flower snarks J_n. They also conjectured that the only generalized Petersen graphs with cop number 2 are GP(n,1), GP(6,2), GP(8,2), GP(9,3) and GP(12,3).

The upper bound uses a three-cop 'rolling wall' strategy. It works on any graph whose vertices form a cycle of columns, each column dominated by a single vertex. Lower bounds come from the Aigner–Fromme argument and from explicit robber safe sets for GP(3k,k) and GP(4k,k) with k≥4. The main results are formalized in Lean 4/Mathlib, with the cop game defined as a least fixed point, robber wins certified by safe sets, and the GP(12,4) certificate checked by kernel evaluation.

c(J_3)=2, and c(J_n)=3 for all n≥5; the lazy cop number of J_n is also 3 for n≥5. The conjecture on generalized Petersen graphs is proved. The flower snark theorem and all lower bounds are verified in Lean using only the standard axioms, and the results are cross-checked by two independent exhaustive solvers.