1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! While waiting for an answer I stumbled upon the non-isomorphic trees as well, so I appreciate your other example a lot! $\endgroup$ – limeeattack May 21 at 15:27
  • 1
    $\begingroup$ If you have access to Mathematica, then the database used by the GraphData[] command has precomputed Tutte polynomials for all the graphs it contains, so that makes it easy to find more examples. $\endgroup$ – Misha Lavrov May 21 at 15:33
1
$\begingroup$

Call two graphs Tutte-equivalent if their Tutte polynomials coincide. Here is some Macaulay2 (M2) code for partitioning connected graphs on $n$ vertices via Tutte-equivalence. Once you have M2 installed and running just copy and paste the code below (changing $n=7$ to your favorite value of $n$).

{"Nauty", "Visualize", "Matroids"} / needsPackage -- load the necessary packages; ignore warnings
openPort "8080" -- needed for Macaulay2 to communicate with the default web browser
n = 7; -- number of vertices
S = ZZ[vars (0..n-1)]; -- a polynomial ring

-- use nauty to get all nonisomorphic connected graphs on n vertices
graphsOnN = generateGraphs (n, OnlyConnected => true); 

-- need to convert the graphs into a format the Matroids package understands
Gn = graphsOnN / (G -> stringToGraph (G,S)) / (G -> graph G#"edges"); -- the conversion

-- construct a common ring for all Tutte polynomials and a function mapping into that ring
tutteRing = ring tuttePolynomial matroid first random Gn;
comparableTutte = T -> sub (T, tutteRing);

-- now we partition all connected graphs via their Tutte polynomials
tuttePartition = partition (g -> comparableTutte tuttePolynomial matroid g, Gn);
tutteEquivalentHash = select (tuttePartition, v -> #v > 1 );
tutteEquivalentList = values tutteEquivalentHash;

Let's look at the data quickly. First we can check that out of the $853$ connected non-isomorphic graphs on $7$ vertices, $428$ are Tutte-unique, i.e., share their Tutte polynomial with no other graph (well, technically, no other connected graph on seven vertices).

# select (values tuttePartition, v -> #v === 1)

More generally we can see how many blocks of the partition of each size we have by entering

apply (values tuttePartition, v -> #v) // tally

which yields the output

Tally{1 => 428}
      2 => 42
      3 => 22
      4 => 12
      5 => 9
      6 => 3
      7 => 6
      9 => 1
      10 => 2
      11 => 3
      12 => 2
      18 => 2

We can use the command visualize to examine graphs in each block. For example, the graphs in one of the largest blocks are intimately related to dart and kite examples given by @Misha. If we enter the following

L = select (tutteEquivalentList, v -> #v == 18);
visualize L#0#0

then a browser window opens showing the following "three-headed dart"

whose Tutte polynomial, not surprisingly, is $x^3(x^3+2x^2+2xy+y^2+x+y)$.

For a more interesting example, the two graphs of the first block of size two are:

They share the Tutte polynomial $$x^{6}+5 x^{5}+5 x^{4} y+5 x^{3} y^{2}+5 x^{2} y^{3}+3 x y^{4}+y^{5}+10 x^{4}+15 x^{3} y+14 x^{2} y^{2}+9 x y^{3}+3 y^{4}+10 x^{3}+16 x^{2} y+12 x y^{2}+4 y^{3}+5 x^{2}+7 x y+3 y^{2}+x+y.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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