对于图G=(V,E)中的边e∈E,我们记G-e表示将边e删除后得到的新图G',G/e表示将e删除,并将e的两个端点合并为一个点后得到的新图(如图所示,G/(u,v)即为u,v合并为w后得到的图)。
需要注意的是,合并操作会保留所有的重边,即在上图操作后,w向外连边数为8而不是7。特别地,若u,v之间有多条重边,则G/(u,v)只会删去其中一条,其余的重边将构成新图中w指向自己的自环。
图G=(V,E)的Tutte多项式是一个关于变量x,y的多项式,满足:
①若E=φ,则T(G;x,y)= 1
②若e是G的一个桥边,则T(G;x,y)=xT(G-e,x,y)
③若e是G的一个自环,则T=(G;x,y)=yT(G-e;x,y)
④若e既不是桥边,也不是自环,则T(G;x,y)=T(G-e;x,y)+T(G/e; x,y)
容易证明,一张图G的Tutte多项式是唯一的。设K4(V, E)为四阶完全图,e∈E,则K4-e的Tutte多项式可能是( )。