WorksMathematics
The cop number of the flower snarks, and the generalized Petersen graphs with cop number two
Abstract
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 has cop number for every , and that has cop number . 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 is for . Second, we prove the conjecture of Morris, Runte and Skelton that the only generalized Petersen graphs with cop number are and the four graphs , , and . The new ingredient is an explicit robber strategy showing that two cops do not suffice on and for . The theorem on flower snarks and all of the new lower bounds have been formally verified in the Lean 4 proof assistant.
Introduction
In the game of Cops and Robbers, introduced by Nowakowski and Winkler [8], a team of cops tries to catch a robber on a finite graph. Both sides move along edges and see everything. The cop number is the least number of cops that can guarantee a capture. Aigner and Fromme [1] showed that graphs of girth at least 5 and minimum degree have . For background see the book of Bonato and Nowakowski [3].
The generalized Petersen graphs are cubic, and they have been a testing ground for the game. Ball, Bell, Guzman, Hanson-Colvin and Schonsheck [2] proved that for all . Morris, Runte and Skelton [7] showed that the bound 4 is attained by most generalized Petersen graphs of girth 8. They ended their paper with several open questions. Two of them are answered here. The first concerns another family of cubic graphs, the flower snarks of Isaacs [5].
Problem 1.1 ([7], Problem 6.6). What is the cop number of the flower snark ?
Theorem 1.2. , and for every . Moreover, the lazy cop number of is 3 for every .
(Isaacs’s flower snarks are the graphs with odd, since only those are snarks. The theorem holds for every .)
An earlier public, AI-generated exploration on ProbXiv [10] also states for odd and sketches a guarded-column strategy similar to the one below. That entry reports no human examination. Our flower-snark treatment additionally proves the lazy-cop statement and the even- extension, states the general cyclic-decomposition lemma, and includes formal verification. We cite the entry as a prior public claim, not as a peer-reviewed proof.
The second question is a conjecture stated in the same paper [7 p. 221]. A generalized Petersen graph is never cop-win, and it can have cop number 2 only if its girth is 3 or 4. All such graphs with are known [2].
Conjecture 1.3 (Morris, Runte, Skelton [7]). The only generalized Petersen graphs with cop number 2 are for and , for .
Theorem 1.4. Conjecture 1.3 is true. Equivalently, if then and .
Methods
The lower bound follows from the Aigner–Fromme argument once one knows that has girth at least 5 for . The upper bound is the substance of Theorem 1.2. In , the vertex is adjacent to , so it dominates the “column” , and every edge joins two equal or consecutive columns. A cop on is therefore a wall the robber cannot cross. Two such walls confine the robber, and a third cop moves the walls closer together (Lemma 3.5).
For Theorem 1.4 the girth-3 and girth-4 cases are and . There the Aigner–Fromme argument fails, and we replace it by an explicit set of safe positions for the robber, which he can stay inside forever (§ 4).
Verification
The statement “ for all ” has been formally verified in Lean 4 with Mathlib [4, 11], for every , without computer search (§ 6).
So has the statement “ unless or is one of the four listed pairs”.
All the results were also checked by exhaustive computation for small parameters, using two independent solvers (§ 5).
Preliminaries
All graphs are finite and simple. is the neighbourhood of and is the closed neighbourhood. We say that dominates if .
The game
A game with cops on a graph goes as follows.
The cops choose vertices (not necessarily distinct).
The robber then chooses a vertex.
The cops and the robber then move alternately, starting with the cops. In a move, every cop (respectively the robber) stays put or moves to an adjacent vertex.
The cops win if at some point a cop occupies the robber’s vertex. The cop number is the least such that cops have a strategy that wins against every robber. In the lazy variant at most one cop moves on each cop turn [9]. The lazy cop number is defined in the same way. Clearly .
A position consists of the multiset of cop vertices and the robber’s vertex , with the cops about to move. To show that cops do not suffice we use the following standard principle.
Lemma 2.1. Let be a set of positions for cops such that:
(a) (placement) for every there is an with ;
(b) (safety) if then no cop of dominates ;
(c) (closure) if and is obtained from by a cop move, then there is with .
Then the robber can evade cops forever, so .
Proof. The robber starts at a vertex given by (a) and then always replies as in (c). By (b), when the cops are about to move, none of them is on or next to the robber. So the cops’ move cannot reach the robber. After the robber’s reply the position is again in , so by (b) the robber is not standing on a cop.
Theorem 2.2 (Aigner–Fromme [1]). If has girth at least 5 and minimum degree at least 3, then .
For completeness we recall the proof in the form we shall reuse.
Proof. Let be the set of positions in which no cop dominates the robber.
Closure. Suppose and the cops move to . No cop of is on . Let be a vertex. If contained two neighbours of , there are two cases.
If , then span a triangle.
Otherwise is a 4-cycle.
Both are impossible. So each cop dominates at most one of the at least three neighbours of . The robber moves to an undominated neighbour, and the new position is in .
Placement. Here we need a vertex dominated by neither cop. For a cubic graph with more than 8 vertices one exists, since two closed neighbourhoods contain at most 8 vertices. (For see also Lemma 3.2(c).)
Lemma 2.1 now applies with $k=2.
Flower snarks
Definition 3.1 ([5]). Let . The graph has the vertices , , , with , and the following edges (indices of taken modulo ):
, , for every (the claws);
for every (the inner -cycle);
and for , together with and (the outer -cycle ).
For odd , is the flower snark.
The column of a vertex is .
Lemma 3.2. Let .
(a) is exactly column , and every edge of joins two vertices whose columns are equal or differ by modulo .
(b) If , then has girth at least 5 (in fact 5 for and 6 for ).
(c) Every closed neighbourhood contains at most one vertex of .
Proof. (a) The first claim is immediate. Claws stay inside a column. The edges , and join consecutive columns, and the two twist edges join column to column 0.
(c) The -vertices are pairwise non-adjacent, and each other vertex has exactly one -neighbour.
(b) We show that no cycle of length at most 4 passes through an -vertex. Cycles avoiding the -vertices lie in the inner -cycle or the outer -cycle, so they are long.
Suppose a short cycle passes through , with cycle-neighbours in .
These three vertices are pairwise non-adjacent, so the cycle is not a triangle.
For a 4-cycle, and would need a common neighbour . Apart from , the neighbours of are -vertices, while those of lie on the outer cycle. So , and is on the outer cycle.
On the outer $2n$-cycle, and are at positions and . A common neighbour would require , which is impossible for $n \ge 3.
Figure 1. The flower snark . The dashed edges and join the -path and the -path into one 10-cycle. Column is the claw .
Finally, the inner and outer cycles have lengths and .
The exact values of the girth were confirmed by computer for . □
The lower bound
Proposition 3.3. For , two cops cannot catch the robber on . Hence .
Proof. is cubic with girth at least 5 by Lemma 3.2(b), so Theorem 2.2 applies. For placement, two cops dominate at most two of by Lemma 3.2(c), and the robber starts on the third. □
The hypothesis is needed. contains the triangle , and contains the 4-cycle .
The upper bound: the rolling wall
We prove the upper bound for a class of graphs that contains every .
Definition 3.4. A cyclic dominated decomposition of a graph into columns is a map together with vertices such that:
(i) each vertex is dominated by ;
(ii) every edge satisfies , or .
By Lemma 3.2(a), the columns of form such a decomposition. Its key consequence is the following.
A cop on is a wall. If the robber ever enters column , he is next to that cop, who captures him on the following move. Hence a robber who wants to survive never enters column .
Lemma 3.5 (Rolling wall). If is connected and has a cyclic dominated decomposition, then three cops win on . They win even in the lazy game, so .
Proof. Call the cops , and (back wall, front wall, mover). All three start on .
Throughout, if the robber is dominated by some cop at the start of a cop turn, that cop moves onto him and the game ends.
Otherwise exactly one cop moves, as described below. So the strategy is lazy.
We keep an integer , initially 0, and maintain the following.
Invariant. At each cop turn, is on , is on , and the robber is in a column in .
The invariant holds at the start. After the robber places, either he is in column 0 and is caught at once, or he is in a column in .
The robber cannot leave the interval. Suppose the invariant holds and only moves. If the robber steps out of , then by (ii) he enters column or column 0. There he is dominated by or , by (i), and is captured on the next turn.
A phase. By connectivity, walks along a path to , one edge per turn, while and stand still. During the walk the invariant is preserved, by the previous paragraph. When arrives on there are two cases.
If the robber is in column , dominates him and captures him.
Otherwise he is in a column in .
We now rename the cops: becomes the new front wall, becomes the new mover, and increases by one. The invariant holds again.
Termination. Each phase is finite and increases . When the interval is empty, so the robber must already have been caught. □
Proof of Theorem 1.2. For , Proposition 3.3 gives . Lemmas 3.5 and 3.2(a) give . Since , both are equal to 3.
For , exhaustive computation (§ 5) shows that one cop loses and two cops win on . Two independent programs agree on this. □
Remark 3.6. The strategy is wasteful. Each phase moves from to in four steps (via ), and its worst-case capture time is exactly (computed for odd ). The optimal capture time with three cops is much smaller, roughly (Table 1).
| 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | |
| capture time | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 8 | 9 | 10 |
| 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | ||
| capture time | 11 | 11 | 13 | 13 | 14 | 15 | 16 | 16 | 18 |
Table 1. Optimal three-cop capture time on , measured in cop moves. For every odd , two cops lose and three cops win; has cop number 2.
The decomposition idea is close to standard “guard a separator” arguments; compare the proof of in [6]. We have not found Lemma 3.5 stated in the literature, but we do not claim the technique is new.
Generalized Petersen graphs with cop number two
For and , the generalized Petersen graph [12] has outer vertices and inner vertices (). Its edges are , and . Thus
Lemma 4.1 (cf. [2]). Let . Then has girth at most 4 if and only if or .
Proof. Every cycle uses an even number of spokes . Consider the short cycles by the number of spokes they use.
No spokes. The cycle lies in the outer -cycle, so its length is ; or it lies in the inner graph. A short inner cycle needs or . Since , this means or .
Two spokes, length 4. The cycle is , which needs . That is excluded.
Two spokes, length 3. This is impossible.
Theorem 4.2. If , two cops cannot catch the robber on or on .
We first show how Theorem 1.4 follows.
Proof of Theorem 1.4 from Theorem 4.2. The listed graphs have cop number 2.
For , and this is in [2] (by hand).
For and it is also in [2] (by computer). We confirmed all four of the small cases with two independent solvers.
Now let with not listed. There are two cases.
If , then is cubic of girth at least 5 by Lemma 4.1, so by Theorem 2.2. Placement holds since .
Otherwise , and by Theorem 4.2.
The safe set
Fix or with . For an index put and
A cop that can step into in one move and is not in lies in . We also define
Let denote the inner triangle when , and let be the antipode of on its inner 4-cycle when . Then is the set of vertices outside from which a cop can step onto a vertex dominating both inner neighbours of : a vertex of , or .
Let be the set of positions such that:
(S1) no cop dominates ; and
(S2) if is an inner vertex, it is not the case that one cop is in and the other is in .
In words, a robber on is threatened only if one cop guards the exit to the outer rim while the other guards both inner exits. (S2) forbids exactly this combination.
Index facts
Put if , and if . All indices are modulo , and ranges over . Each fact below says that some small integer combination of is not . Each is checked directly and holds under the stated hypothesis.
(F1) , and .
(F2) .
(F3) , and .
(F4) .
(F5) is disjoint from . This set is if , and if .
(F6) .
For example:
(F4) fails only if with . That forces with , which is impossible for .
(F6) fails only if with . For this forces , and indeed (F6) fails for , where .
Proof of Theorem 4.2
We verify the three conditions of Lemma 2.1. Safety is (S1).
Placement.
A cop on dominates three outer vertices, and a cop on dominates one.
Since , some outer vertex is undominated. (S2) is vacuous there.
Closure. Let , and let the cops move to . We write for the new position of a cop .
Case 1: . No cop of is on .
If some vertex of is undominated by , the robber moves there.
Otherwise, since , the only vertices other than that dominate two vertices of are and . So one cop is on, say, , and the other dominates without being on . Hence both cops lie in . The robber moves to .
(S1) holds by (F1).
(S2) holds because (F2), so neither cop is in .
Case 2: . By (S1) no cop of is in , so no cop of is on .
Case 2a. If no cop of is in , then is undominated, and the robber moves to .
Case 2b. Otherwise, let be a cop with , and let be the other cop.
was in .
So, by (S2) for , was not in . By (S1), was not in either.
By (F1) and (F4), dominates neither nor , and .
We claim that there is that does not dominate and with .
First, . Otherwise by (F3).
Hence, by (F3), dominates at most one of .
If dominates , then . Take , so by (F5).
If dominates neither, then by (F6) lies outside at least one of and . Take to be the corresponding vertex.
The robber moves to , which is legal since .
(S1) holds at , since neither cop dominates it.
(S2) holds at , since neither cop is in .
This proves closure for with and for with .
The case . Here (F6) fails, and so does the claim in Case 2b. We use instead the safe set obtained from by also forbidding, for a robber on , the eight cop pairs
A direct enumeration of all 300 cop placements and 24 robber vertices verifies conditions (a)–(c) of Lemma 2.1 for . This finishes the proof. □
Remark 4.3. For every , the set (respectively ) coincides exactly with the set of positions from which the robber can evade two cops, as computed by an exhaustive solver. The robber’s replies described above were also replayed mechanically against every cop move for .
Computations
We computed the outcome of the game by retrograde analysis of the game graph, which gives the exact winning region and the exact capture time. Two independent programs were used. They share no code, and each builds the graphs from the definitions. They agree on every case that both computed.
Flower snarks. Two cops lose and three cops win on for every odd . One cop loses and two cops win on . The lazy cop number of is 3 for ; note that .
Generalized Petersen graphs. Two cops lose on and for (up to 320 vertices), and three cops win for . Two cops win for .
Formal verification
The statement
is proved in Lean 4 using Mathlib [4, 11]. The proof assistant reports that it depends only on the standard axioms (propositional extensionality, choice and quotient soundness). It uses no computer search.
The game. A position is cop-winning if it lies in the least set of positions that is closed under “the cops can move so that every robber reply leads into the set”. Defined this way, a winning position means capture is forced in finitely many moves.
Robber wins. These are certified by a safe set as in Lemma 2.1. We prove that the two notions exclude each other.
The lower bound. This is the argument of Theorem 2.2. The local facts for are discharged by linear arithmetic, uniformly in .
The upper bound. This is Lemma 3.5, proved for an abstract cyclic dominated decomposition. The proof is by induction on the number of remaining columns, with an inner induction on the walk taken by the mover.
Fidelity of the definition. The formal definition of follows Definition 3.1 literally. Its edge set was exported and checked to be isomorphic to the graphs used in § 5.
The results of § 4 are formalised in the same development. The formal statement says that if , and , then every winning team of cops on has at least three cops. Hence .
Girth at least 5. When , the hypotheses of the Aigner–Fromme argument are again proved by linear arithmetic. The four graphs with are handled by direct evaluation.
and . The safe set and the case analysis of § 4 are formalised uniformly in .
. The certificate is checked by the Lean kernel itself. This is a kernel evaluation, not compiled code, so it adds no axioms.
Axioms and fidelity. All of these theorems depend only on the three standard axioms. The formal was checked to have exactly the textbook edge set for several .
The matching upper bounds ( for the listed graphs, from [2]) are not formalised.
Concluding remarks
Capture time. The optimal capture time of three cops on grows roughly like , but irregularly (Table 1). What is it exactly?
Lazy cops. Theorem 1.2 determines the lazy cop number of , giving a partial answer to the snark analogue of [7 Problem 6.3]. The lazy cop number of generalized Petersen graphs remains open.
Dominated decompositions. Lemma 3.5 applies to any graph that maps onto a cycle with dominated fibres. Which other snark families, or other cubic graphs, admit such a decomposition, possibly after contracting a bounded set?
Acknowledgements
Anthropic Claude assisted with proof-strategy exploration, manuscript drafting, computational checks, and Lean formalization; the author takes responsibility for the results.
San José State University
Email address: [email protected]
References
- [1]M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Mathematics 8 (1984), no. 1, 1–12.DOI
- [2]Taylor Ball, Robert W. Bell, Jonathan Guzman, Madeleine Hanson-Colvin, and Nikolas Schonsheck, On the cop number of generalized Petersen graphs, Discrete Mathematics 340 (2017), no. 6, 1381–1388.arxiv.org/abs/1509.04696
- [3]Anthony Bonato and Richard J. Nowakowski, The game of cops and robbers on graphs, Student Mathematical Library, vol. 61, American Mathematical Society, Providence, RI, 2011.
- [4]Leonardo de Moura and Sebastian Ullrich, The Lean 4 theorem prover and programming language, Automated Deduction – CADE 28, Lecture Notes in Computer Science, vol. 12699, Springer, 2021, pp. 625–635.DOI
- [5]Rufus Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, The American Mathematical Monthly 82 (1975), no. 3, 221–239.DOI
- [6]Gwenaël Joret, Marcin Kamiński, and Dirk Oliver Theis, The cops and robber game on graphs with forbidden (induced) subgraphs, Contributions to Discrete Mathematics 5 (2010), no. 2.
- [7]Joy Morris, Tigana Runte, and Adrian Skelton, Most generalized Petersen graphs of girth 8 have cop number 4, Australasian Journal of Combinatorics 83 (2022), no. 2, 204–224.
- [8]Richard Nowakowski and Peter Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics 43 (1983), no. 2–3, 235–239.DOI
- [9]David Offner and Kerry Ojakian, Variations of cops and robber on the hypercube, Australasian Journal of Combinatorics 59 (2014), no. 2, 229–250.
- [10]AI-generated exploration of the cop number of the flower snarks, ProbXiv, https://probxiv.com/problems/most-generalized-petersen-graphs-of-girth-8-have-cop-number-4-3, 2026, Public comment dated 17 August 2026; the page states that no person has examined it.
- [11]The mathlib Community, The Lean mathematical library, Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), 2020, pp. 367–381.DOI
- [12]Mark E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, Journal of Combinatorial Theory 6 (1969), 152–164.DOI
