# 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

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