Distinguishing graphs with simple spectrum by homomorphism counts

• No fixed-treewidth, bounded-Euler-genus, or K7-minor-free class is complete on simple spectrum; any complete class needs unbounded treewidth and Euler genus and a K7 minor.Source: §1 · p. 2
• Attaching rooted trees to Cai–Fürer–Immerman pairs yields non-isomorphic simple-spectrum pairs indistinguishable over minor-closed classes preserving the original pair’s indistinguishability.The pairs can be cospectral, bipartite, nonsingular, and of maximum degree at most six.Source: §1 · p. 2
• It remains open whether every class complete on simple spectrum must contain graphs with arbitrarily large clique minors.Source: §1 · p. 2
• Subcubic homomorphism counts determine every graph of nullity at most one up to isomorphism, including every graph with simple spectrum.Source: §1 · p. 2
• Subcubic indistinguishability is characterized by equal vertex counts and a bijective linear isometry between adjacency-matrix images that intertwines adjacency operators and preserves coordinatewise trilinear forms.Source: §1 · pp. 2–3
• Whether the nullity-at-most-one theorem extends to nullity two is open, while counterexamples exist at nullity three.Source: §1 · p. 3
• The single-vertex graph and subdivisions of connected cubic graphs have subcubic distinguishing power when every complete graph is a minor of some sequence member.Source: §1 · p. 3
• Including the single-vertex graph is necessary: K2 and K2 ⊔ K1 have simple spectra but equal counts from every connected graph with at least two vertices.Source: §1 · p. 3

• Whenever CFI0(B) and CFI1(B) are indistinguishable over a minor-closed class, there are non-isomorphic indistinguishable witnesses with simple spectrum, bipartite, cospectral, nonsingular, and of maximum degree at most six.Source: §2 · p. 4
• For bounded-treewidth, bounded-Euler-genus, and K7-minor-free classes, the proof selects connected base graphs B with indistinguishable CFI pairs [13, Theorem 10 and Lemma 12], [14, Lemma 2.10 and proof of Theorems 1.8–1.9], [16, Theorem 1.7 and Section 1.3].Source: §2 · p. 4
• Attaching the same rooted graph to every vertex in each CFI fibre preserves indistinguishability; the proof reduces homomorphism counts to lifts from a quotient that is a minor of the source graph.Source: §2 · pp. 4–5
• Rooted subcubic caterpillars generated from rooted K2 by operations X and Y can avoid any finite list of prescribed values hT(λj), enabling spectral control in the rooted products.Source: §2 · pp. 5–6
• For weighted connected bases with distinct vertex sets, suitable attached trees yield nonsingular rooted products with simple, pairwise disjoint spectra; eigenvalue multiplicities are governed by the kernel dimension in Lemma 7.Source: §2 · p. 8

Proof of Theorem 1

• A fibre-basis change partitions the vertex-function space into U0 and Ue subspaces, making each invariant and yielding the block diagonal adjacency matrix in Equation (24).The blocks correspond to the graphs bS0 and bSe; the tree attachments contribute tree adjacency blocks, while root-coordinate matrices give the corresponding base-graph blocks.Source: §2 · p. 10
• The rooted products are non-isomorphic, bipartite, cospectral, nonsingular, have simple spectrum, and have maximum degree at most six.Their non-isomorphism follows because their maximal subgraphs of minimum degree at least two are the non-isomorphic CFI graphs; attaching trees preserves bipartiteness.Source: §2 · p. 11

Remark 11

• Remark 11 states that arbitrarily large clique minors suffice for completeness; an affirmative answer to whether they are necessary would imply the weak Roberson conjecture [15, Conjecture 5 and Theorem 8.4].Lemma 4 also gives non-isomorphic simple-spectrum C-equivalent graphs when a minor-closed class admits a connected B with CFI0(B) ≡C CFI1(B).Source: §2 · p. 12

3 Proof of Theorem 2

• For any multigraph, counts into two graphs agree on every simple subdivision exactly when their labelled spectral coefficients agree for every edge labelling.The proof expands subdivision counts in spectral projectors and uses linear independence of the powers λ^m for m ≥ 3.Source: §3 · pp. 12–13
• Equality of degree-two/three tensor-network values for every such multigraph is equivalent to a bijective linear isometry intertwining adjacency and preserving the trilinear form.The network assigns the adjacency bilinear form to degree-two vertices and the trilinear form to degree-three vertices.Source: §3 · p. 13
• Equal subcubic homomorphism counts are equivalent to adjacency-image equivalence and to equal vertex counts plus matching labelled coefficients for every connected cubic multigraph.Adjacency-image equivalence requires a bijective linear map between adjacency images that preserves the inner product and trilinear form and intertwines the adjacency operators.Source: §3 · pp. 13–15
• Equal cubic tensors identify the same set of unit rows of a matrix with orthonormal columns.The lemma characterizes unit vectors ξ for which κ(ξ) = 1 as precisely the unit rows.Source: §3 · p. 16
• For nullity-one graphs, matching kernel-support sizes, exterior reduced rows, and support-row sums implies matching reduced rows on the supports.This is the stated conclusion of Lemma 15 under its listed assumptions.Source: §3 · p. 17

Proof of Theorem 2

• For nullity at most one, im-equivalence forces isomorphism by matching nonzero-eigenspace data and reconstructing the graphs’ reduced rows.The proof handles the nonsingular case directly and treats nullity one by aligning the missing kernel-vector coefficients or comparing support rows.Source: §3 · pp. 19–21
• Subcubic homomorphism counts determine graphs of nullity at most one up to isomorphism, and thus distinguish every graph with simple spectrum.Equal subcubic counts imply im-equivalence and then isomorphism; isomorphic graphs have equal homomorphism counts. Simple spectrum forces nullity at most one.Source: §3 · p. 22
• The nullity bound cannot extend to three: non-isomorphic 14-vertex CFI graphs of nullity three are indistinguishable over D3 [15].Whether the theorem extends to nullity two remains open; exhaustive search found no indistinguishable non-isomorphic pair on at most 11 vertices.Source: §3 · p. 22

Proof of Proposition 3

• A subsequence with HN containing K3N as a minor contains a subdivision of every connected cubic multigraph H with at most N vertices.A simple subcubic subdivision J of H can be chosen with at most 3N vertices and embedded using the clique minor.Source: §4 · p. 22
• Replacing each edge of H with a chain of diamonds yields subdivisions with at least m + 1 possible internal-vertex counts per edge.The paths for different edges have disjoint interiors, and at least one edge of X remains outside the chosen subdivision.Source: §4 · p. 23
• Summing over subdivision-path vertices turns spectral-projector factors into powers of Mλ,K/τK, while vertices outside the paths contribute powers of τK.The total exponent of τK is |V(X)| − |V(H)|, independent of the path lengths.Source: §4 · pp. 24–25
• Interpolation over path lengths and sequence sizes replaces operator powers by image projectors and removes scalar weights.The proof uses the available path-length choices and the unbounded vertex counts of the sequence.Source: §4 · pp. 25–26
• Equality of labelled coefficients on the sequence transfers to every connected cubic multigraph by interpolation and induction over target components.The transfer applies to every nonzero edge labelling.Source: §4 · pp. 26–27
• Counts from K1 and subdivisions of the sequence distinguish graphs exactly as subcubic counts do when each HN contains K3N as a minor.The proof first obtains equality of labelled coefficients on every connected cubic multigraph, then applies Lemma 12 and Theorem 2.Source: §4 · pp. 22, 26, 27

Declarations

• GPT-6 Astra assisted with mathematical exploration and identifying relevant literature.The author formulated the problem and initial theorem statements.Source: Declarations · p. 27
• The proofs were developed through discussions between the author and GPT-6 Astra.Source: Declarations · p. 27
• GPT-6 Astra and Claude Opus 5.5 assisted with readability and presentation, and the author assumes responsibility for all content.Source: Declarations · p. 27