Searching for Graph Counterexamples with Mixed-Extension Templates

A large counterexample can be easier to find through its construction than through its individual edges. We investigate this approach using mixed extensions, in which each vertex of a small graph is replaced by a clique or an independent set. Their spectra can be computed from small quotient matrices. We compare hill climbing with nested rollout policy adaptation (NRPA) on 15 development tasks, checking candidate counterexamples with rational and interval arithmetic. With ten seeds per task, a 16-cell cap and an order cap of $10^4$, hill climbing finds verified counterexamples in 131/150 runs and NRPA in 75/150. At order cap 30, the counts are 120 and 47. Each run includes verification within a 120-second budget. We also recheck 498 archived objects, finding equality artifacts and an incorrect polynomial-peak definition. We prove two infinite counterexample fam- ilies; the other sampled families have only finite evidence. The five highlighted Laplacian refutations reproduce prior work. These experiments show how both the search algorithm and the allowed graph order affect performance. A separate learned-restart experiment remains exploratory because its tasks influenced model development.