Harary and Akiyama asked whether there exists a non self-complementary (SC) graph $G$ having the same chromatic polynomial as its complement.

It was later shown that there indeed exist such graphs and it was conjectured that all such graphs have the same degree sequence as their complement.

As it turns out this conjecture is false and for every $n \geq 9$ congruent to $0,1$ modulo 4 one can construct a graph having the same chromatic polynomial as its complement but different degree sequence.

Extending this problem, it is possible to show that for any $n \geq 8$ congruent to $0,1$ modulo 4 there exist a non SC graph having the same *Tutte polynomial* as its complement.

What I currently cannot solve is the following

Question 1.Is there a graph $G$ having different degree sequence from $\overline{G}$ but the same Tutte polynomial?

~~ ~~

Question 2.Is there a non SC graph having the same Tutte polynomial as its complement and order congruent to $0$ modulo $4?$

What I basically tried was generating all non SC graphs with $n(n-1)/4$ edges and checked the respective Tutte polynomials. As it turns out such a graph has to have order $n \geq 12$ and there are way too many graphs to be checked by a standard computer in this manner. Hence I need a more clever approach for searching. A nice thing would be if I could quickly filter through the output of nauty, removing graphs with the same degree sequence as their complement. I am afraid Sage is too slow for that.

I recall someone on MO (G. Royle?) saying that the Tutte polynomial is not ''good'' at distinguishing degree related invariants hence I suspect that the answer to Question 1 is positive.

**Edit.** The paper solving the original question of Akiyama and Harary is this one. While the thing for the Tutte polynomial can be found in this preprint. I would like to point out that it is just a preprint hence it may contain errors.

5more comments