Non-isomorphic graphs with same Tutte polynomial

graph theorygraph-isomorphismpolynomials

I've been looking for some non-isomorphic graphs with the same Tutte polynomial. I'm aware of this thread and this thread, however my understanding of matroids is non-existent, and they are a bit beyond the scope of the courses I'm taking.

If anybody could give me an example of a pair of non-isomorphic graphs with the same Tutte polynomial, I would be forever grateful.

Best Answer

As mentioned on Wikipedia, the Tutte polynomial of any tree with $m$ edges is $x^m$. So take any two non-isomorphic trees of the same size, and you'll have the example you want.

As a random other example, the dart graph and the kite graph (shown below) both have Tutte polynomial $x^2 + 2 x^3 + x^4 + x y + 2 x^2 y + x y^2$:

enter image description here

Related Question