# Counterexample for graph isomorphism using eigenvalue multiplicity (connected graphs)

Two graphs $G_1$ and $G_2$ that are cospectral (eigenvalue multisets from their adjacency matrices are the same), do not have to be isomorphic. The pair of cospectral graphs that serve as the smallest counterexample to isomorphism are the disjoint graph union of $C_4 \cup K_1$ and the star graph $S_5$.

What is the smallest counterexample known when we require that $G_1$ and $G_2$ are connected?

• Here's a counterexample with $8$ vertices. – joriki Feb 7 '12 at 22:28
• @joriki I saw that one after I posted the question, is it known to be the smallest for all connected graphs or just polyhedral ones? – Hooked Feb 7 '12 at 22:58

## 1 Answer

Harary, King, Mowshowitz, Read, Cospectral graphs and digraphs, Bull London Math Soc 3 (1971) 321-328, give an example of two connected, cospectral, nonisomorphic graphs on 6 vertices, and claim, on the basis of exhaustive search, that it's the smallest.

EDIT: Here's the example. Let the vertices be $A,B,C,D,E,F$. For one graph, join $A$ to each of the other vertices, then join $BC$ and $DE$. For the other, draw a path $ABCDE$, then join $F$ to $B,C,D$.

• I checked this result (here's the code). This is the only example on $6$ vertices, and indeed the smallest. The characteristic polynomial is $$x^6-7x^4-4x^3+7x^2+4x-1=(x+1)^2(x-1)(x^3-x^2-5x+1)\;.$$ On $7$ vertices there are 31 characteristic polynomials associated with more than one connected graph; only one is connected with three graphs, $$-x^7+11x^5+10x^4-16x^3-16x^2=-x^2(x+1)(x+2)(x^3-3x^2-4x+8)\;;$$ the edges are A-B A-C A-D A-E C-E D-E A-F C-F D-F A-G B-G; A-C B-C B-D A-E B-E C-E D-E B-F C-F D-F A-G; A-B A-C B-C A-E B-E C-E D-E C-F D-F A-G B-G. – joriki Feb 8 '12 at 7:25
• Ok so how about using the Eigen values and degree sequence together? in fact for speed purposes you would do the degree sequence first. There has to be a way to prove/disprove that if both those qualities are the same then the graphs are isomorphic. – Rob Nov 19 '15 at 17:38
• @Rob, I'm sure there are nonisomorphic graphs that have the same degree sequence and the same eigenvalues. No one has ever found a finite list of invariants to characterize graph isomorphism, and no one expects to. Have you read the Harary et al. paper? – Gerry Myerson Nov 20 '15 at 12:26
• No I have not, but I will go look it up. I am an amateur at best :). I am about to dive into the recorded lectures discussed in this article sciencenews.org/article/new-algorithm-cracks-graph-problem – Rob Nov 20 '15 at 14:44