Project Euler Problem 690
Tom (the cat) and Jerry (the mouse) are playing on a simple graph G.
Solution
Answer: 415157690
A key observation is that a Tom graph is exactly a cop-win graph (also called a dismantlable graph) in the graph-search literature: Tom can guarantee capture of an invisible moving Jerry iff the graph admits a dismantling order by repeatedly removing a vertex whose closed neighborhood is contained in another vertex’s neighborhood.
Counting unlabeled Tom graphs then becomes a combinatorial species/enumeration problem over dismantlable graph components. The resulting counting sequence matches the known enumeration of Tom graphs:
$$1,1,2,3,6,10,20,37,76,153,328,\dots$$
which agrees with the problem values
$$T(3)=3,\quad T(7)=37,\quad T(10)=328,\quad T(20)=1416269.$$
Evaluating the induced recurrence/generating-function computation modulo $1,000,000,007$ for $n=2019$ gives:
Answer: 412463428