Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|cite|improve this question
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 1

up vote 5 down vote accepted

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$.

share|cite|improve this answer
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 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 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 – Rob Nov 20 at 14:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.