Why can’t I compute the Tutte polynomial as described in a paper

graph theorypolynomials

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$.

Related Question