A quantum isomorphic pair of non-isomorphic graphs needs at least ten vertices

Abstract

Two graphs are quantum isomorphic when the isomorphism game between them has a perfect quantum-commuting strategy. Such a pair need not be isomorphic: Atserias, Mančinska, Roberson, Šámal, Severini and Varvitsiotis turned the Mermin magic square into a quantum isomorphic, non-isomorphic pair of graphs on 24 vertices. How small can such a pair be? Writing N for the least order of one, the published bracket is 6 ≤ N ≤ 24, and it is restated in that form by an expert paper of October 2025. We prove N ≥ 10. The proof exhibits six connected planar graphs on at most six vertices — the bull, the path P₆, one further tree and three unicyclic graphs — whose homomorphism counts take pairwise distinct values on the 288 248 isomorphism classes of graphs on 5,6,7,8 and 9 vertices, and then applies the forward direction of Mančinska and Roberson's theorem that quantum isomorphism is exactly equality of homomorphism counts from planar graphs. The two halves are logically separate, and we keep them separate. The combinatorial half — that these six graphs separate every pair of non-isomorphic graphs on five to nine vertices — is proved outright here, modulo one imported fact, that nauty's catalogues of small graphs are complete; the planarity of each of the six is certified by an explicit integer straight-line drawing rather than cited. The transfer to quantum isomorphism is the one ingredient we do not prove, and it appears as an explicit hypothesis of the theorem rather than in a remark. Everything below except a handful of elementary steps, each named where it occurs, is machine-checked in Lean 4, in a development that uses neither the axiom of choice nor sorry. The bracket becomes 10 ≤ N ≤ 24; nothing here says anything about 10 itself.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   f78d32683d240db4ae848158ed96c846edb0b1ed01fc70df0629793443563d17