Why the following two graphs have the same flow polynomials and the same Tutte Polynomials.

Question

Please consider the following two graphs

I am obtaining that the two graphs have the same flow polynomial given by

$$\left(\lambda -1\right) \left(\lambda -2\right) \left(\lambda -3\right) \left(\lambda^{5}-15 \lambda^{4}+95 \lambda^{3}-323 \lambda^{2}+602 \lambda -497\right)$$

From other side I am obtaining that the two graphs have the same Tutte polynomial given by

My question is: why these two graphs have the same flow polynomial and Tutte polynomial?

Answer 1

The two graphs are isomorphic; for such reason they have the same Tutte polynomial; and then, the same flow polynomial.

The adjacency matrix for the first graph is given by

$$ \left[\begin{array}{cccccccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{array}\right]$$

The adjacency matrix for the second graph is given by

$$\left[\begin{array}{cccccccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{array}\right]$$

The difference between the two adjancency matrices is given by

$$ \left[\begin{array}{cccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 & -1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & -1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 & -1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 & -1 & 1 & 0 & 0 \end{array}\right]$$

The last matrix can be reduced to the null matrix using the following permutation over the nodes of the second graph:

$[1 = 8, 2 = 12, 3 = 9, 4 = 13, 5 = 10, 6 = 14, 7 = 11, 8 = 1, 9 = 5, 10 = 2, 11 = 6, 12 = 3, 13 = 7, 14 = 4]$

As a result of the permutation, the two adjacency matrices will be the same.

Given that the adjacency matrices of the two graphs are the same, then these two graphs are isomorphic.

Answer 2

The two graphs are indeed isomorphic as Juan said, I have another point of view maybe you'll like it more?
If you check the path of the polygon in the middle, it visits each vertices in the middle (each time).
For the first you have the path $p_1 =(8,10,12,14,9,11,13)$ and for the second the cycle $p_2 = (8,11,14,10,13,9,12)$ so if you consider the permutation $\sigma \in \mathfrak{S}_{14}$ verifying $$ \sigma_{|\{8,\dots,14\}} = \begin{pmatrix} p_1 \\ p_2\end{pmatrix} = \begin{pmatrix} 8&10&12&14&9&11&13 \\ 8&11&14&10&13&9&12\end{pmatrix} = \begin{pmatrix} 8&9&10&11&12&13&14 \\ 8&13&11&9&14&12&10\end{pmatrix}= \begin{pmatrix} 8&13&11&9&14&12&10\end{pmatrix}$$

You then just need to ensure that each vertices in the middle is connected to the right vercite on the exterior.

You had for the first graph $1-8, 9-2, \dots$, but since we change the order, e.g. $9$ goes to $13$, we have to ensure the $2$ moves to $6$. So define $$\sigma_{|\{1,\dots,7\}} = (n \mapsto n-7) \circ \sigma_{|\{8,\dots,14\}} \circ (n \mapsto n+7)$$.

Your $\sigma$ induces an iso on your graphs. And you have the matrix of $\sigma$ in $GL_n (Z)$ that is exactly the matrix of your iso