I am trying to compute the Tutte polynomial of a graph
as described in a paper and Wikipedia, but don't get experimental support.
Paper p.9 and Wikipedia
relate the Tutte polynomial of a graph to another polynomial.
If $(x-1)(y-1)=z$, $$T(G;x,y)=F_G(z,y)/H(G)$$
Where $F_G(z,y)=\sum_{A \subseteq E}z^{c(G_A)}(y-1)^{|A|} $
where $c(G)$ is the number of connected components and $H(G)$ has simple
closed form.
Experimentally I can't compute the Tutte polynomial using this approach. The results for the Tutte polynomial are wrong
Why?
For example for $K_3$ the code computes $F_{K_3}=y^3 z-z+1$ and I verified this by hand.
Any bugs in this sagemath program?
def tutte_to_hyper(g):
def ra(g): return g.order() - g.connected_components_number()
def cg(g): return g.connected_components_number()
def nu(g): return g.size() - ra(g)
SS=Subsets(g.edges(0))
K.<y,z>=QQ[]
su=0
rae=ra(g)
ve=list(g.vertices())
for S in SS:
S=list(S)
#if len(S)==0: continue
ve=uniq(flatten(S))
F=g.subgraph(ve,edges=S)
su += z**cg(F)*(y-1)**len(S)
return su,(y-1)**ra(g)*z**cg(g)
Best Answer
From my understanding in wikipedia, you never change the vertex set for your graph, you only change the edge set. So if the edge set $A$ is empty, in case of the $K_3$ you get 3 vertices, no edges, so 3 components. This may be the reason you are not getting exponents of $z$ higher than 1. This is also the definition in your paper, on page 7. "Let $G = (V, E)$ be a graph and $A \subseteq E$. Identify $A$ with the spanning subgraph $G_A = (V, A)$." The vertex set of $G_A$ is still the complete $V$.