
\documentstyle[12pt,fleqn]{article}

%Definizioni Latex Anna 

\newtheorem{Definition}{\bf Definition}[section]
\newtheorem{Example}[Definition]{\bf Example}
\newtheorem{Remark}[Definition]{\bf Remark}
\newtheorem{Lemma}[Definition]{\bf Lemma}
\newtheorem{Theorem}[Definition]{\bf Theorem}
\newtheorem{Corollary}[Definition]{\bf Corollary}
\newtheorem{Proposition}[Definition]{\bf Proposition}

\textwidth 15.6 cm   %**************
\textheight 20 cm  %**************
\oddsidemargin 0.4 cm  %**************
\topmargin 0.6 cm  %**************

\newcommand{\bform}{\begin{displaymath}}
\newcommand{\eform}{\end{displaymath}\smallskip}
\newcommand{\beqn}[1]{\begin{equation}\label{#1}}
\newcommand{\eeqn}{\end{equation}\smallskip}
\newcommand{\beqna}[1]{\begin{eqnarray}\label{#1}}
\newcommand{\eeqna}{\end{eqnarray}\smallskip}
\newcommand{\beqnan}{\begin{eqnarray*}}
\newcommand{\eeqnan}{\end{eqnarray*}\smallskip}
\newcommand{\tr}[1]{#1^{\scriptscriptstyle T}}
\newcommand{\rif}[1]{(\ref{#1})}
\newcommand{\vect}[2]{\left(\begin{array}{c} #1\\#2 \end{array}\right)}
\newcommand{\done}{\hfill$\Box$\par}

\def\Re{I\!\!R}
\def\gt{>}
\def\lt{<}
\def\sp{\;\;}
\def\wug{=^{\!\!\!\!\!^{2}}}
\def\wnug{\ne^{\!\!\!\!\!^{2}}}
\def\prec{<^{\!\!\!\!\!^{L}}}
\def\prece{\le^{\!\!\!\!\!^{L}}}


\begin{document}


\begin{titlepage}
\title{\large {\bf A Theory Of Pfaffian Orientations II:
  $T$-joins, Edge-Cuts, And A Duality of Enumeration. }} 




\author{
       \normalsize {\bf Anna Galluccio}\\
       {\normalsize Istituto di Analisi dei Sistemi ed} \\
       {\normalsize Informatica - CNR}\\ 
       {\normalsize viale Manzoni 30}\\
       {\normalsize 00185 Roma}\\
        {\normalsize ITALY} 
\and
\thanks{Supported by DONET, GACR 0194 and GAUK 194}
   \normalsize {\bf Martin Loebl}\\
   {\normalsize Department of Applied Mathematics }\\
   {\normalsize Charles University}\\
   {\normalsize Malostranske n. 25}\\
   {118 00 Praha 1}\\
   %{\normalsize and University of Waterloo }\\
   {\normalsize CZECH REPUBLIC}
}

\maketitle

\begin{abstract}
This is a continuation of our paper `A Theory of Pfaffian Orientations I'.
 We present a new combinatorial way to compute the generating
 functions of $T$-joins and edge-cuts of graphs.
 As a consequence we show that the computational problem
 to find the size of a maximum edge-cut is polynomially
 solvable for the graphs which may be drawn on an arbitrary
 fixed orientable surface. We also survey the 
 related results concerning a duality of the Tutte polynomial
 and we give  interesting expressions for the chromatic polynomial
 and the flow polynomial of a graph.
 In a continuation of this paper which is in preparation
 we present an application
 to the Ising problem of three-dimensional crystal structures.
\end{abstract}

\end{titlepage}

\section{Introduction}

 We start by repeating basic notions and theorems of \cite{GL6}.
$G=(V,E)$  will always be a graph and $x_e$ will be a variable 
associated with each
 edge $e$ of $G$.  We let $x=(x_e;e\in E)$ be the vector of the 
variables associated with the edges of $G$. For $M\subset E$ let $x(M)$ denote the product
 of the variables of the edges of $M$. An {\it orientation} of graph $G=(V,E)$
is a digraph obtained from $G$ by giving an orientation to each
 edge of $G$. 
 
Let $A\Delta B$ denote the symmetric difference of the sets $A$ 
and $B$.  


\begin{Definition}
The {\it generating function
 of the perfect matchings} of $G$ is polynomial ${\cal P}(G,x)$ equal
 to the sum of $x(P)$ over all perfect matchings $P$ of $G$.
\end{Definition}

\medskip

 Given a graph
 $G=(V,E)$, an eulerian subgraph of $G$ is any graph $G'=(V,E')$
 with $E' \subset E$ and all degrees even.

\begin{Definition}
The {\it generating function
 of  eulerian subgraphs} of $G$ is polynomial ${\cal E}(G,x)$ equal
 to the sum of $x(U)$ over all eulerian subgraphs $U$ of $G$.
\end{Definition}

Given a graph $G=(V,E)$ and $T\subset V$, a $T$-join is any graph
$G'=(V,E')$ such that $E'\subset E$ and the degree of a vertex $v$
 of $G'$ is odd iff $v\in T$. Eulerian subgraphs are $T$-joins
 for $T=\emptyset$.


\begin{Definition}
 Let $G=(V,E)$ be a graph and $T\subset V$.
The {\it generating function
 of  $T$-joins} of $G$ is polynomial ${\cal T}_T(G,x)$ equal
 to the sum of $x(W)$ over all $T$-joins $W$ of $G$.
\end{Definition}



\medskip

Next we consider multicuts.

\begin{Definition}
 Let $k\geq 1$ and let $G=(V,E)$ be a graph. A pair $(\{V_1,...,V_k\},E')$
 is called {\it $k$-cut} if $\{V_1,...,V_k\}$ is a partition of $V$ 
 into $k$ non-empty disjoint subsets
 and $E'$ is the set of all edges
 with the end-vertices in different parts $V_i$, $i=1,...,k$.
\end{Definition}


\begin{Definition}
The {\it generating function
 of $k$-cuts} is  polynomial ${\cal C}_k(G,x)$ equal
 to the sum of $x(C)$ over all $k$-cuts $(\{V_1,...,V_k\},C)$ of $G$.
\end{Definition}

\medskip

\begin{Definition}
 Let $G$ be a graph and let $D$ be an orientation of $G$. Let $M$ be a perfect
 matching of $G$. For each perfect matching $P$ of $G$ let
$sgn(D,M\Delta P)=(-1)^n$ where $n$ equals to the number of 
clockwise even alternating cycles
 of $M\cup P$ and let ${\cal P}(D,M)$ equals the sum of
$sgn(D,M\Delta P) x(P)$ over all perfect matchings $P$ of $G$.
\end{Definition}

\begin{Definition}
Let $G$ be a graph and $D$ be an orientation of $G$. Denote by $A(D)$
the skew-symmetric matrix with the rows and the columns indexed by 
$|V(G)|=2n$, where $a_{vw}=x_{(v,w)}$ in case $(v,w)$ is an arc of $D$, 
$a_{vw}= -x_{(v,w)}$ in case $(w,v)$ is an arc of $D$, and $a_{vw}=0$
otherwise. 

The {\it Pfaffian} of the skew-symmetric matrix $A(D)$ is defined as 
 
$$Pf(A(D))=\sum_{P} s^*(P)a_{i_1j_1} \cdots a_{i_nj_n}$$
 
\noindent
where $P=\{\{i_1j_1\},\cdots,\{i_nj_n\}\}$ is a partition of the 
set $\{1,\dots,2n\}$ into pairs and $s^*(P)$ equals to the sign 
of the permutation $(i_1j_1\dots i_nj_n)$.

Each nonzero term of the expansion of the Pfaffian of $A(D)$ 
equals $x(P)$ or $-x(P)$ where $P$ is a perfect matching of $G$. 
Let $s(D,P)$ equal the sign of the term $x(P)$ so that 

$$Pf(A(D))=\sum_{P} s(D,P)x(P)$$ 

\end{Definition}

The following theorem was proved by Kasteleyn (\cite{KAST2}). 

\begin{Theorem}
\label{Kastel} 
Let $G$ be a graph and $D$ an orientation of $G$. Let $P,M$ be two 
perfect matchings of $G$. Then
$$s(D,P)=s(D,M)sgn(D,M\Delta P).$$

\noindent
Hence, 
$$Pf(A(D)=\sum_{P} s(D,P)x(P)=s(D,M)\sum_{P} sgn(D,M\Delta P)x(P)=
s(D,M){\cal P}(D,M)$$.
\end{Theorem}

The following theorem is well-known (see \cite{lp}).

\begin{Theorem}
Let $G=(V,E)$ be a graph and let $D$ be its orientation. 
Then $Pf^2(A(D)) = det(A(D))$.
\end{Theorem}

Kasteleyn (\cite{KAST2}) introduced the following notion.

\begin{Definition}
Graph $G$ is called {\it Pfaffian} if it has a {\it Pfaffian} orientation,
 i.e. an orientation such that each alternating cycle with respect 
to an arbitrary
 fixed
 perfect matching $M$ of $G$ has an odd number of edges oriented clockwise.
\end{Definition}

\medskip

 Hence if a graph $G$ has a Pfaffian
 orientation $D$ then ${\cal P}(G,x)^2 = det(A(D))$.

Kasteleyn (\cite{KAST2}) also observed that the planar graphs 
have a Pfaffian orientation.

\begin{Theorem}
\label{plpf}
Each planar graph has a Pfaffian orientation.
\end{Theorem}
\medskip\noindent
{\bf Proof.} Let $G$ be a planar graph, and let $M$ be its perfect matching.
 Consider $G$ drawn on the plane.
 Orient edges of $G$ so that each face, except possibly the outer one,
 is clockwise odd. Each such face `encircles' no vertex 
 of $G$. Observe that the orientation has the property
 that a cycle $C$ of $G$ is clockwise odd iff $C$ encircles an
 even number of vertices.
Each alternating cycle with respect to $M$ encircles an even number of vertices
 and hence it is clockwise odd.

\done
\medskip

\begin{Definition}
We define surface $S_g$ , $g$ positive integer, as follows.
 It consists of a {\it base} $B_0$ and $2g$ {\it bridges}
 $B^i_j$, $i=1,...,g$ and $j=1,2$.
$B_0$ is a convex $4g$-gon with vertices
 $a_1, ...,a_n$, $n=4g$, numbered clockwise. Bridge $B^i_1$ is a $4$-gon
with vertices $x^i_1, x^i_2, x^i_3, x^i_4$ numbered clockwise . It is glued 
 with $B_0$ so that edge $(x^i_1,x^i_2)$ of $B^i_1$ is identified with
 edge $(a_{4(i-1)+1},a_{4(i-1)+2})$ of $B_0$ and edge $(x^i_3,x^i_4)$ of $B^i_1$ is identified with
 edge $(a_{4(i-1)+3},a_{4(i-1)+4})$ of $B_0$ . 

 Bridge $B^i_2$ is a $4$-gon
with vertices $ y^i_1, y^i_2, y^i_3, y^i_4$ numbered clockwise . It is glued 
 with $B_0$ so that edge $(y^i_1,y^i_2)$ of $B^i_2$ is identified with
 edge $(a_{4(i-1)+2},a_{4(i-1)+3})$ of $B_0$ and edge $(y^i_3,y^i_4)$ of $B^i_2$ is identified with
 edge $(a_{4(i-1)+4},a_{4(i-1)+5 mod 4g})$ of $B_0$ .
\end{Definition}

\begin{Definition}
\label{embed}
We say that a graph $G$ is a $g$-graph if it may be drawn on $S_g$
 so that all the vertices belong to the  base $B_0$, and 
 each edge uses at most one bridge. 
The set of the edges drawn on the base will be denoted by $E_0=E_0(G)$ and
 the set of edges drawn on bridge $B^i_j$ will be denoted by $E^i_j=E^i_j(G)$.
 
 If moreover the following conditions are satisfied then we say
 that $G$ is a {\it proper $g$-graph}.
\begin{enumerate}
\item[1.]
 The outer face of the subgraph embedded on $B_0$ is a cycle,
 and it is embedded on the boundary of $B_0$,
\item[2.]
 Each vertex is incident with at most one edge out of $E_0$,
\item[3.]
 The subgraph embedded on $B_0$ has a perfect matching.
\end{enumerate}

  If $G$ is a proper $g$-graph then we denote by $C_0$
 the cycle which forms the outer face of $E_0$, and we denote
 by $M_0$ a perfect matching of the subgraph of $G$ embedded
 on $B_0$.
\end{Definition}

\medskip

For each $g$-graph we fix its embedding on $S_g$.

\medskip

\begin{Definition}
Let $G=(V,E)$ be a proper $g$-graph. The graphs $G_0=(V_0,E_0)$ 
and $G^i_j=(V,E_0\cup E^i_j)$ are planar.  
We define orientations of $G_0$ and
 $G^i_j$ as follows: orientation $D_0$ of $G_0$ is Pfaffian and 
such that each face of $G_0$ is clockwise odd (as in the proof 
of Theorem~\ref{plpf}).
 Next we draw $G^i_j$ on the plane so that the drawing of $G_0$ is 
 unchanged,
 and edge $(x^i_1,x^i_4)$ ($(y^i_1,y^i_4)$ respectively)of $B^i_j$
 belongs to the outer face
 of the drawing of $G^i_j$. Now complete $D_0$ to an orientation
 of $G^i_j$ according to Theorem~\ref{plpf}, i.e. so that
 each face is clockwise odd. This defines orientation 
 $+D^i_j$ of the edges of $E^i_j$.

 $-D^i_j$ is defined obviously by reversing the orientation
 of $+D^i_j$.
\end{Definition}

\begin{Remark}
If $G$ is a proper $g$-graph and Pfaffian orientation $D_0$ of $G_0$ 
 is fixed, then for each $ij$ $+D^i_j$ is uniquelly determined.
\end{Remark}


\begin{Definition}
Let $G$ be a proper $g$-graph, $g \geq 1$. An orientation $D$ of $G$
 which equals to $+D^i_j$ or $-D^i_j$ on $E^i_j$ and to $D_0$ 
 on $E_0$ is called {\it relevant}. We define its type 
 $r(D) \in \{+1,-1\}^{2g}$ as follows.
For $i =0,..g-1$ and $j =1,2$, $r(D)_{2i + j}$ equals to $+1$ or $-1$
 according to the sign of $D^{i+1}_j$ in $D$.
\end{Definition}


\begin{Definition}
Let $G=(V,E)$ be a proper $g$-graph and let $A$ be a subset of its edges. We define its type $t(A) \in \{+1,-1\}^{2g}$
 as follows. For $i =0,..g-1$ and $j =1,2$, we let $t(A)_{2i + j}$ equal to
 $(-1)^{s(A)_{2i+j}}$, 
 where $s(A)_{2i+j}$ equals to the number of edges of $A$
 which belong to $E^{i+1}_j$. 
\end{Definition}

\begin{Definition}
Let $r=(r_1,...,r_{2g})$ and $r_i\in \{1,-1\}$.
We let $c(r)=(-1)^n 2^{-g}$, where
$n=|\{i;r_{2i+1}=r_{2i+2}=-1\}|$.
\end{Definition}
 
 
\medskip 
The following theorem and its corollary are the main results of 
\cite{GL6}.

\begin{Theorem}
\label{pm}
Let $G$ be a proper $g$-graph.
 Then ${\cal P}(G,x)$ equals
 to linear combination ${\cal L}'_g(G,x)$ of $Pf(A(D))$, where $D$
 is a relevant orientation of $G$.
 The coefficient of ${\cal L}'_g$ at $Pf(A(D))$
 equals to $s(D,M_0) c(r(D))$. Moreover $s(D,M_0)$ is constant
 for each relevant orientation $D$ of $G$. 
\end{Theorem}
\medskip

\begin{Corollary}
\label{genus}
Let $G$ be a graph of orientable genus $g$. Then ${\cal P}(G,x)$
may be expressed using Theorem~\ref{pm}.
\end{Corollary}


The following proposition is a consequence of Theorem~\ref{plpf}.

\begin{Proposition}
Let $D$ be a relevant orientation of a proper $g$-graph $G$ and 
let $P,M$ be two perfect matchings of $G_0$. Then $s(D,P)=s(D,M)$.
\end{Proposition}

This Proposition implies that the following definition is correct.

\begin{Definition}
\label{coeff}
Let $D$ be a relevant orientation of a proper $g$-graph $G$. Then 
we let $c'(D)=s(D,M_0) c(r(D))$ be the coefficient of $Pf(A(D))$
in ${\cal L}'_g(G,x)$.
\end{Definition}





\section{$T$-joins.}

In this section let $G=(V,E)$ be a graph and let $T\subset V$.

We generalize a construction of Kasteleyn (\cite{KAST1}).

\begin{Definition}
Let $G$ be a $g$-graph. Construct $g$-graph $G^T_1$ from $G$ so that
 each vertex $v$ of $G$ is replaced by a cycle $C(v)$ of length $d(v)$.
  If $deg_G(v)$ is even and $v \notin T$ or
 $deg_G(v)$ is odd and $v\in T$ then $d(v)=deg_G(v)$. 
 Otherwise $d(v)=deg_G(v)+1$.

If  $e_1,...,e_k$ are the edges of $G$ incident with $v$,
listed in the clockwise order, 
and $(z_1,...,z_{d(v)})$ is an order of the vertices of $C(v)$ 
then we let $e_i$ incident with $z_i$ in $G_1^T$. In this way 
each edge of $G$ incident with $v$ is incident with one vertex
 of $C(v)$ in $G^T_1$. $G^T_1$ is a $g$-graph and each $C(v)$ is
 a face of its planar part $E_0(G^T_1)$.

 Next, let $G^T$ be the graph obtained from $G^T_1$ by adding all the
 edges between the vertices of each $C(v)$, $v$ vertex of $G$.
 Hence in $G^T$, each $C(v)$ is replaced by a complete graph
 with the same vertices. This complete graph will be denoted by $K(v)$. 
 Finally we let $x^T_e=1$ for each edge of $G^T-G$ and $x^T_e=x_e$ 
 for each edge of $G\cap G^T$. We denote by $x^T_1$ the 
restriction of $x^T$ to the edges of $G^T_1$.
  
 Let $F_1$ denote a Pfaffian orientation of $E_0(G^T_1)$ such that each
 face of $E_0(G^T_1)$ is clockwise odd (as in Theorem~\ref{plpf}).
 Particularly each $C(v)$ is clockwise odd in $F_1$.

 Let $e$ be an edge of $K(v)-C(v)$. 
 Orient it so that both cycles it forms with
 $C(v)\subset F_1$ are clockwise odd. Note that this is always possible
 since $C(v)$ is clockwise odd in $F_1$.
 This gives an orientation  of $G_0$ and of the edges of all $K(v)$,
 $v$ vertex of $G$. Denote it by $F_2$.

 Let $D$ be an orientation of $G^T$. We denote by $D^1$
 the restriction of $D$ to $G^T_1$.
 We will call an orientation $D$ of $G^T$ {\it $T$-relevant} 
 if $F_2\subset D$ and the restriction $D^1$ of $D$
 is a relevant orientation of $G^T_1$.

\end{Definition}



\begin{Theorem}
\label{es}
 Let $G$ be a graph such that $G^T_1$ is
 a proper $g$-graph. 

Then ${\cal T}_T(G,x)$ equals
 to linear combination ${\cal L}^T_g$ of  $Pf(A(D))$, where $D$
 is a $T$-relevant orientation of $G^T$ and the coefficient
 of $Pf(A(D))$ equals to the coefficient $c'(D^1)$ of $Pf(A(D^1))$
 in ${\cal L}_g'(G^T_1,x_1^T)$.
\end{Theorem}

\medskip\noindent
{\bf Proof.}
Let $D$ be a $T$-relevant orientation of $G^T$.
 Each term of $Pf(A(D))$ equals to $x^T(P)$ 
 or $-x^T(P)$ where
 $P$ is a perfect matching of $G^T$. We remind that $s(D,P)$ denotes
 the sign of $x^T(P)$ in $Pf(A(D))$.

 Let $P$ be a perfect matching of 
 $G^T$ and let $P'=P\cap E(G)$. Then $P'$ is a $T$-join of $G$,
 and $x(P')=x^T(P)$. 
 
 If $W$ is a $T$-join of $G$ then $W$ is a matching of $G^T$ which
 may be completed into a perfect matching.
 Let ${\cal R}(W)$ denote the set of the perfect matchings of $G^T$
 which contain $W$. 
 
 Each ${\cal R}(W)$ is non-empty and
 there are in general many ways in which $T$-join $W$
  may be completed into a perfect matching of $G^T$.

 Let $W$ be a $T$-join of $G$. 
 Let $v \in V$. Let $V(W,v)$ be the set of vertices of $K(v)$ not incident
 with an edge of $W$. Then $|V(W,v)|$ is even.
 Let $K(W,v)$ be the complete subgraph of $G^T$ induced on
 $V(W,v)$ and let $D(W,v)$ be the orientation of $K(W,v)$ induced by the
 $T$-relevant orientations of $G^T$.

 Consider the arcs of $D(W,v)$ drawn inside the face $C(v)$ of 
$E(G^T_1)$.

 Observe that $D(W,v)$ has a non-intersecting clockwise odd
 Hamiltonian cycle $H(W,v)$: this is true since
 $C(v)$ is clockwise odd in any relevant orientation of $G^T$,
and each arc of $D(W,v)-C(v)$ is by definition directed so that both
 cycles if makes with $C(v)$ are clockwise odd.

Let $G_1^T(W)=G_1^T \cup (H(W,v);v \in V)$.  
$G^T_1(W)$ is a proper $g$-graph
and each $H(W,v)$ is a face of its planar subgraph. Let $D_0(W)$ denote
 the restriction of $F_2$ to the planar subgraph $E_0(G^T_1(W))$
 of $G^T_1(W)$. All faces of $D_0(W)$ are clockwise odd and hence 
$D_0(W)$ is a Pfaffian orientation.
 
The remaining arcs of $D(W,v)-H(W,v)$ may be drawn
 inside the area bounded by $H(W,v)$ and they are directed in $D(W,v)$
 so that the two cycles they form with $H(W,v)$ are clockwise odd.
 
Let $W(v)$ be a perfect matching of $H(W,v)$ and let
 $M(W)=W\cup (W(v);v\in V)$ be a perfect matching of $G_1^T(W)$
 (and $G^T$ as well) which contains $W$.

\medskip
{\bf Claim 1.}
Let $W$ be a $T$-join of $G$ and let $D$ be a $T$-relevant 
 orientation of $G^T$. Then
 $$\sum_{P \in {\cal R}(W)} s(D,P)= s(D,M(W)).$$
\medskip\noindent
{\bf Proof.}
Let $P \in {\cal R}(W)$. By Theorem \ref{Kastel} we have
 $$s(D,P)= sgn(D,M(W)\Delta P) s(D,M(W))= (-1)^n s(D,M(W)),$$
 where $n$ equals to the number of clockwise even alternating cycles
 of $P$ and $M(W)$. Each such alternating cycle
 belongs to $D(W,v)$ for some
 vertex $v$ of $G$. We let $P(W,v)=P\cap D(W,v)$ and we let ${\cal M}(W,v)$
 denote the set of the perfect matchings of $D(W,v)$. 

  We have
$$\sum_{P \in {\cal R}(W)} s(D,P)=$$
$$s(D,M(W))\sum_{P \in {\cal R}(W)}\prod_{v\in V} 
sgn(D(W,v),W(v)\Delta P(W,v))=$$
$$s(D,M(W))\prod_{v\in V} \sum_{P \in {\cal 
M}(W,v))}sgn(D(W,v),W(v)\Delta P).$$
 

It suffices to show that 
$\sum_{P \in {\cal M}(W,v)} sgn(D(W,v),W(v)\Delta P)=1$ for each $v\in V$.

We will prove it by induction on $|V(W,v)|$. 

If $|V(W,v)|=2$ then it is clearly true.

Hence let $|V(W,v)|>2$ and let $e=xy$ be an edge of $W(v)$. 

 First observe that
 $\sum_{P\in {\cal M}(W,v),e\in P} sgn(D(W,v),W(v)\Delta P)=1$ by the induction
 assumption for $D(W,v)-\{x,y\}$.

 The perfect matchings of $D(W,v)$ which do not contain $e$
 are paired as follows.

 Each  perfect matching of $D(W,v)$ not containing $e$
 may be obtained from a perfect matching $M'$ containing $e$ and 
another edge $f$ disjoint with $e$, by replacing  $e$ and $f$  by other 
two disjoint edges with the same end-vertices.
This replacement may be done in two ways,
 which produces a natural pairing of the  perfect matchings
 of $D(W,v)$ which do not contain $e$. 

  Let $M_1,M_2$ be a pair of perfect matchings
 of $D(W,v)$ obtained by replacing $e,f \in M'$ 
  by edges $e_1,f_1$ and $e_2,f_2$ respectively. 
Observe that the drawing of $f$ inside face $H(W,v)$ of $G^T_1(W)$
 doesnot intersect $e$, since $e$ is an edge of $H(v)$. Hence the edges
 of exactly one of the pairs $e_1,f_1$ and $e_2,f_2$
 intersect when we draw
 them inside face $H(W,v)$ of $G^T_1(W)$. Let it be $e_1,f_1$.

In order to simplify the presentation we will write $a\wug b$ if $a=b$
 modulo $2$.

  By the definition of $sgn$ we have 
$$sgn(D(W,v),W(v)\Delta M_1)+sgn(D(W,v),W(v)\Delta 
M_2) \wug 1+sgn(D(W,v),M_1\Delta M_2) \wug 0$$
 since there is exactly one alternating cycle $Q$ of $M_1\Delta M_2$, and it
 is clockwise even. This may be proved as follows: 
 
 Let $Q'$ denote cycle $(e_2,e,f_2,f)$ of $D(W,v)$. $Q'$ is clockwise odd
 since $e_2,f_2$ do not intersect, $H(W,v)$ is clockwise odd
 and each arc of $D(W,v)-H(W,v)$ is by definition directed so that both cycles
 it makes with $H(W,v)$ are clockwise odd. From the same reason all
 four cycles of $D(W,v)$, each consisting of $e_1$ or $f_1$
 and two arcs of $Q'$ are clockwise odd.
 This implies that $Q$ is clockwise even and thus 
  $sgn(D(W,v),M_1\Delta M_2)=-1$.   
 
 Summarising we have $\sum_{P\in {\cal}M(W,v),e\notin P}  
 sgn(D(W,v),W(v)\Delta P) =0$.

{\bf End of Claim 1.}

\medskip

 Let $W$ be a $T$-join of $G$.
 Let $D'_1,...,D'_{4^g}$ be the relevant orientations of $G_1^T(W)$
 containing $D_0(W)$. Let $x^W$ denote the restriction of $x^T$ to the edges
 of $G_1^T(W)$.

 By \ref{pm},  ${\cal P}(G^T_1(W),x^W)$ equals the sum over all 
perfect matchings $P$ of $G^T_1(W)$ of 
$\sum_{i=1}^{4^g} c'(D'_i) s(D'_i,P)x^W(P)$ where
$c'(D'_i)=s(D'_i,M(W))c(r(D'_i))$.

Hence $\sum_{i=1}^{4^g} c'(D'_i) s(D'_i,M(W))=1$.

For each $D'_i$, $i=1,...,4^g$, there is
 exactly one $T$-relevant orientation $D_i$
 of $G^T$ such that $D'_i\subset D_i$. We have that 
 $s(D'_i,M(W))=s(D_i,M(W))$. Finally observe that
 $c'(D'_i)=c'(D^1_i)$: $r(D'_i)=r(D_i^1)$ and 
 $s(D'_i,M(W))=s(D'_i, M_0(G_1^T))=s(D_i^1, M_0(G_1^T))$.

Hence we get

{\bf Claim 2.} $$\sum_{i=1}^{4^g} c'(D^1_i) s(D_i,M(W))=1.$$

{\bf End of Claim 2.}
 
In summary, the linear combination ${\cal L}^T_g$
 of $Pf(A(D))$, where $D$ are the $T$-relevant orientations of $G^T$,
 equals to the sum of $\alpha(W)x(W)$ over the $T$-joins $W$ of $G$, and
 by Claims~1 and 2, 

$$\alpha(W)= \sum_{i=1}^{4^g} \sum_{P\in {\cal R}(W)} c'(D_i^1)) 
s(D_i,P)=1$$.
This proves the Theorem.

\done

\bigskip

\begin{Corollary}
\label{coro}
Let $G=(V,G)$ be a graph of orientable genus $g$, and let $T\subset V$.
Then ${\cal T}_T(G,x)$ may be expressed using Theorem~\ref{es}.
\end{Corollary}
\medskip\noindent
{\bf Proof.}
We proceed in a similar way as in the proof of Corollary~\ref{genus}
given in \cite{GL6}.

If $G$ has orientable genus $g$ then it may be embedded on $S_g$
so that each vertex belongs to $B_0$, but some edges may use several
bridges. We construct graph $G'$ so that we replace
each edge $e$ which uses $k$ bridges, $k\geq 1$, by a path $P_e$
consisting of new edges $(e_1,...,e_{2k+1})$. 
We let $x'_{e_i}=1$ for each $i>1$ and $x'_{e_1}=x_e$.
Next we add edges so that the outer face of the planar part is
 a cycle. We let $x'_e=0$ for each such edge $e$.  

Observe that ${\cal T}_T(G,x)={\cal T}_{T}(G',x')$, $G'$ is a $g$-graph
and each vertex of $G'$ is incident with at most one edge
which does not belong to $G'_0$.

If $T=\emptyset$ then $G'^T_1$
 is a proper $g$-graph since each $C(v)$ has a perfect matching,
 and we can use Theorem~\ref{es} to get ${\cal T}_T(G',x')={\cal 
 T}_T(G,x)$.

 If $T\neq \emptyset$ we need to work more. We construct a graph 
$G''$ as follows. Let $|T|=2k$ 
 be even, otherwise $G$ has no $T$-join. 
 We connect pairs of vertices of $T$ embedded on $B_0$ 
 by disjoint lines $L_1,...,L_k$ on $B_0$ such that
 the interior of each $L_i$, $i=1,...,k$, contains no vertex of $G'$.
 Let $L_i$ connect vertices $x_i,y_i$ of $T$. 

For each $i\in \{1,...,k\}$ we 
 do the following construction. Let $z_1,...,z_m$ be the intersections
 of $L_i$ with the lines representing the edges of $G'_0$, ordered
 along $L_i$  from $x_i$ to $y_i$. Let $f_j$ be the edge of $G'_0$
 containing $z_j$, $j=1,...,m$ and let $z'_j$ be a vertex of the
 interior of the line representing $f_j$ which is located on the right 
 hand-side of $z_j$
 when staying on $L_i$ and looking towards $y_i$. Moreover let
 $z'_j$ be sufficiently near to $z_j$.
 We add vertices $z_1,z'_1,...,z_m,z'_m$ to $G'$, replacing
 each edge $f_j$ by the corresponding path of an even number of 
 new vertices. 
 As before, if $f_j$ is replaced by path $(f_j^1,...,f_j^p)$ then we let
 $x''_{f_j^1}=x'_{f_j}$, $x''_{f_j^l}=1$ for $l>1$ and $x''_e=x_e$ 
 for each edge of $G'$.
 
 Moreover we add edges 
 $x_iz_1, z'_1z_2, ... ,z'_{m-1}z_m, z'_my_i$ to $G''$ and we let 
 $x''_e=0$ for each such edge $e$.

 This finishes the construction of $G''$.

 Let $R_i $ denote the path 
 $x_iz_1, z_1z'_1, z'_1z_2, z_2z'_2, ... , z_mz'_m, z'_my_i$ of 
 $G''$.

Observe that
 ${\cal T}_{T}(G'',x'')={\cal T}_{T}(G',x')$, the outer face
 of $G''_0$ is a cycle and each vertex of $G''$ is incident with
 at most one edge which does not belong to $G''_0$. Moreover 
 ${\cal R}= \{R_1,...,R_k\}$ 
 is a $T$-join of $G''_0$. Each path $R_i$ has the property
 that for each vertex $v$ of $R_i$, the edges of $R_i$ incident with $v$
 are neighbouring in the clockwise order of the edges incident with $v$.
Hence $G''^T_1$ is a proper $g$-graph and we may use 
Theorem~\ref{es} to get ${\cal T}_T(G'',x'')={\cal T}_T(G,x)$.

This finishes the proof of the corollary. 

\done


\section{The Multicuts.}

We start with a theorem of van der Waerden (see \cite{vdW}, \cite{w2}, 
\cite{KAST1}). We use the following standard notation.

$sinh(x)=1/2(e^x-e^{-x})$, $cosh(x)=1/2(e^x + e^{-x})$, 
$th(x)=sinh(x)/cosh(x)$ and $coth(x)=cosh(x)/sinh(x)$.

We let $\delta(x,y)$ equal to $1$ if $x=y$ and $-1$ otherwise.
 
If $G=(V,E)$ is a graph and $A\subset E$ then we let
$$U_k((V,A))=\sum_{\sigma \in \{1,...,k\}^V}(\prod_{(ij) \in A} 
\delta(\sigma_i\sigma_j)).$$
 
\begin{Theorem}
\label{c1}
Let $G=(V,E)$ be a graph and $k>1$. 
$$e^{\sum_{f\in E} x_f}[k+\sum_{i=2}^k i!{k\choose i}{\cal C}_i(G,(e^{-2x_f}:f\in E))]=$$
$$(\prod_{f \in E} cosh(x_f)) \sum_{A \subseteq E}
(U_k((V,A))\prod_{f \in A}th(x_f)).$$
\end{Theorem}
\medskip\noindent
{\bf Proof.}
We use a simple fact that 
$$e^{x\delta(\sigma_i\sigma_j)}=cosh(x)+\delta(\sigma_i\sigma_j) sinh(x).$$

We have:
$$e^{\sum_{f\in E} x_f}[k+\sum_{i=2}^k i!{k\choose i}{\cal C}_i(G,(e^{-2x_f}:f\in E))]=$$
$$\sum_{\sigma \in \{1,...,k\}^V}(\prod_{ij \in E}e^{\delta(\sigma_i\sigma_j) x_{ij}})=$$
$$\sum_{\sigma \in \{1,...,k\}^V}(\prod_{ij \in E}(cosh(x_{ij})+
\delta(\sigma_i\sigma_j)
sinh(x_{ij})))=$$
$$(\prod_{f \in E} cosh(x_f)) 
\sum_{\sigma \in \{1,...,k\}^V}(\prod_{ij \in E}(1+\delta(\sigma_i\sigma_j) 
tanh(x_{ij})))=$$
$$(\prod_{f \in E} cosh(x_f)) 
\sum_{\sigma \in \{1,...,k\}^V}\sum_{A \subseteq E}(\prod_{ij \in A}\delta(\sigma_i\sigma_j) tanh(x_{ij}))=$$
$$(\prod_{f \in E} cosh(x_f)) \sum_{A \subseteq E}
(U_k((V,A))\prod_{f \in A}th(x_f)).$$

\done

\medskip

\begin{Theorem}
\label{c2}
 Let $G$ be a graph and let ${\cal C}'_2(G,z)={\cal C}_2(G,z)+1$.
 Then
$$2e^{\sum_{f\in E} x_f}{\cal C}'_2(G,(e^{-2x_f}, f \in E))=$$
$$(\prod_{f \in E} cosh(x_f)) 2^{|V|} {\cal E}(G,(th(x_f): f\in E)).$$
\end{Theorem}
\medskip\noindent
{\bf Proof.} We have from Theorem\ref{c1} that
$$2e^{\sum_{f\in E} x_f}{\cal C}'_2(G,(e^{-2x_f}, f \in E))=$$
$$(\prod_{f \in E} cosh(x_f)) \sum_{A \subseteq E}
(U_2((V,A))\prod_{f \in A}tanh(x_f)).$$

Now observe that 
 if $A \subset E$ is a cycle and $\sigma \in \{1,2\}^V$ arbitrary
 then $\prod_{ij \in A} \delta(\sigma_i\sigma_j) =1$. Hence
 $U_2((V,A))=2^{|V|}$ when $(V,A)$ is an eulerian subgraph. 
 Moreover, if $(V,A)$ is not an eulerian subgraph, then observe that
 $U_2((V,A))=0$.

\done


\medskip

\begin{Theorem}
\label{c3}
Let $G=(V,E)$ be a  graph and let the edges of $G$ be partitioned 
into a bounded number of classes so that the variables $x_f$ are 
equal in each class. Then there is a polynomial algorithm which,
given ${\cal E}(G,x)$ and $G$ as input, produces ${\cal C}_2(G,x)$.
\end{Theorem}
\medskip\noindent
{\bf Proof.}
 We have  
$$(\prod_{f \in E} cosh(x_f)) 2^{|V|} {\cal E}(G,(tanh(x_f): f\in E))=$$

$$(\prod_{f \in E} \frac{e^{x_f}+e^{-x_f}}{2} 2^{|V|} 
{\cal E}(G,(\frac{e^{x_f}-e^{-x_f}}{e^{x_f}+e^{-x_f}}: f\in E))=$$


$$(\prod_{f \in E} \frac{e^{2x_f}+1}{2e^{x_f}} 2^{|V|} 
{\cal E}(G,(\frac{e^{2x_f}-1}{e^{2x_f}+1}: f\in E))=$$

$$2 \prod_{f\in E} e^{x_f}{\cal C}'_2(G,(e^{-2x_f}, f \in E)).$$

Hence, $${\cal C}'_2(G,(e^{-2x_f}, f \in 
E))=2^{|V|-|E|-1}\prod_{f\in E} e^{-2x_f} {\cal E}^*(e^{2x_f}: f\in 
E)),$$
where
$${\cal E}^*(e^{2x_f}: f\in E))=\prod_{f\in E}(e^{2x_f}+1)
{\cal E}(G,(\frac{e^{2x_f}-1}{e^{2x_f}+1}: f\in E)).$$

It follows that ${\cal E}^*$ and, consequently, ${\cal C}'_2$
 and ${\cal C}_2$ may 
be expressed in polynomial time. 

\done

\medskip

Next algorithmical result is a consequence of Theorem~\ref{c3}, 
Corollary~\ref{coro} and Theorem~\ref{es} and Corollary \ref{genus}. 

\begin{Theorem}
\label{algo}
Let $S$ be an orientable surface and $k$ a fixed positive integer. 
Let ${\cal G}$ be the class of graphs which may be embedded on $S$ 
and such that the edges are partitioned into at most $k$ classes
and the variables $x_e$ are equal in each class.
Then ${\cal C}_2(G,x)$ and ${\cal T}_T(G,x)$    
may be determined efficiently for $G\in {\cal G}$. In particular it is
 possible to find efficiently the size of a maximum edge-cut
 for the graphs of ${\cal G}$.
\end{Theorem}

\medskip

\begin{Remark}
 A possibility to understand more about edge-cuts is to try
 to solve the problem of finding
 a maximum weighted edge-cut 
 for the graphs of a fixed surface. This is polynomial for planar graphs
 using the duality of planar graphs and a polyhedral description
 of the Chinese Postman Problem.
\end{Remark}

\medskip

A different construction of Fisher (see \cite{Fish}) also yields 
an algorithm to compute ${\cal C}_2(G,x)$, using 
Theorem~\ref{c3} and  Corollary \ref{genus}.

To split a vertex $v$ of a graph $G$ means to replace $v$ by a path 
of $deg_G(v)$ vertices so that each vertex of the path is incident
 with exactly one edge incident with $v$ in $G$.


\begin{Definition}
Let $G=(V,E)$ be a graph. We denote by $G_s=(V_s,E_s)$ the graph
 obtained from $G$ 
by splitting of all the vertices of $G$. We let 
 $x^s_f=x_f$ for each $f\in G_s\cap G$.
\end{Definition}

All vertices of $G_s$ have degree at most three and 
${\cal C}_2(G,(e^{-2x_f}:f\in E))$ equals the limit of 
${\cal C}_2(G_s,(e^{-2x_f}:f\in E_s)$
 when each $x_f$, $f\in G_s-G$, goes to infinity.
 Moreover, if $G$ is embeddable on 
orientable surface $S$ then so is $G_s$. 

\begin{Definition}
Let $H$ be a graph where each vertex has degree at most three. We 
denote by $H'$ the graph obtained as follows:
\begin{enumerate}
\item let $v$ be a vertex of $H$ of degree two and let $f_1$ and 
      $f_2$ incident with $v$. We delete $v$, add two new vertices 
      $v_1$ and $v_2$ and three new edges $f_1'$, $f'_2$ and $g$.
      $f'_i$ is obtained from $f_i$ by replacing $v$ by $v_i$, 
      $i=1,2$, and $g=v_1v_2$. 
\item let $v$ be a vertex of $H$ of degree three and let $f_1$, 
      $f_2$ and  $f_3$ be the edges incident with $v$. We delete $v$, add 
      six new vertices 
      $v_1,\dots,v_6$ and ten new edges $f_1',f'_2,f'_3$ and 
       $g_1,\dots,g_7$.
      $f'_i$ is obtained from $f_i$ by replacing $v$ by $v_i$, 
      $i=1,2,3$. Moreover, $g_1=v_1v_2$, $g_2=v_2v_4$, 
      $g_3=v_1v_4$, $g_4=v_4v_5$, $g_=v_5v_3$. $g_6=v_3v_6$ and 
      $g_7=v_5v_6$. Hence, $g_1,g_2,g_3$ and $g_5,g_6,g_7$ form 
      triangles.
\end{enumerate}
We let $x'_e=1$ for each $e\in H'-H$ and $x'_e=x_e$ for each $e\in 
H'\cap H$.  
\end{Definition}

\medskip
If $H$ is embeddable on orientable surface $S$ then so is $H'$.

\begin{Proposition}
${\cal P}(H',x')={\cal E}(H,x)$.  
\end{Proposition}

{\bf Proof.} The statement follows from a simple observation that for each 
eulerian subgraph $W$ of $H$ there exists a unique perfect 
matching $P(W)$ of $H'$ such that $W\subset P(W)$.

\done

In summary, if $G$ is a graph embeddable on an orientable surface 
$S$ then so is $G'_s$ and ${\cal C}_2(G,x)$ may be obtained from 
${\cal P}(G'_s,{x^s}')$ by applying Theorem~\ref{c2} (as indicated
 above it is necessary to make a limit for each $x_f$, $f\in E(G'_s)-E(G')$,
 going to the infinity).

${\cal P}(G'_s,{x^s}')$ may be computed using Corollary~\ref{genus}.


\section{A Duality of Enumeration.}

 
Let $V= {\bf F}^n$ be a vector space  over a field ${\bf F}$.
 Each subspace of $V$ is called a {\it linear code of length $n$}.
If linear code $C$ of length $n$ is given as
 the row space of a $(k,n)-$ matrix $A$, i.e. $C=\{A^Tx;x\in {\bf F}^k\}$,
 and $M$ is the matroid
 represented by the columns of $A$, then we let $M=M({\bf F},C)$ and
 $C=C({\bf F},M)$.
 The {\it dual
linear code} $C^*=C({\bf F},M)^*$ is the orthogonal complement of $C$
 in ${\bf F}^n$, i.e. $C^*=\{x\in {\bf F}^n; Ax=0\}$.
% We have $M({\bf F},C^*)=M({\bf F},C)^*$.
 
The elements of a linear code are called codewords.
The weight of a codeword is the number of non-zero entries in it.
If $C$ is a linear code of length $n$ then its {\it weight enumerator}
is the polynomial
$$A_C(t)=\sum_{i=0}^n A_it^i,$$
where $A_i$ denote the number of codewords of $C$ of weight $i$.

\medskip

The following theorem was proved by MacWilliams (\cite{mac}). 

\begin{Theorem}
\label{d3}
Let $C$ be a linear code of length $n$ and dimension $k$ over $GF[q]$
 and let $D$ be its dual code. Then
$$A_D(t)=q^{-k}[1+(q-1)t]^nA_C((1-t)(1+(q-1)t)^{-1}).$$
\end{Theorem}


\medskip

Let $G=(V,E)$ be a graph and let $N(G)$ be the graphic matroid of $G$.
Let $O(G)$ be the oriented incidence matrix of $G$, i.e. $V$ by $E$
 matrix obtained from the incidence matrix of $G$ by replacing exactly one
 $'1'$ of each column by $'-1'$. The columns of $O(G)$ represent
 $N(G)$ over an arbitrary field ${\bf F}$.

 Consider the following example.
 The set of the characteristic vectors of edge-cuts of
 a connected graph $G$ (including
 the empty cut) equals
 $C(GF[2],N(G))$ and
 the set of the characteristic vectors of eulerian subgraphs of $G$
 equals  $C(GF[2],N(G))^*$. 
 Indeed, Theorem \ref{d3} generalises Theorem \ref{c2}.

\medskip

\begin{Theorem}
\label{d4}
Let $G=(V,E)$ be a graph. Then
$$A_{C(GF[q],N(G))}(t)=1 + \sum_{i=2}^q (q-1)...(q-i+1){\cal C}_i(G,(t,...,t)).$$
\end{Theorem}
\medskip\noindent
{\bf Proof.}
Let $C=C(GF[q],N(G))$.
We have $C=\{O(G)^Tx; x\in GF[q]^{V}\}$ and $A_C(t)$ is the weight enumerator
 of $C$. Let us define an equivalence on $GF[q]^V$ by
 $x\equiv y$ if $O(G)^Tx=O(G)^Ty$. Observe that each equivalence class
 consists of $q$ elements since $O(G)^Tx=O(G)^Ty$ if and only if
 $x-y$ is a constant vector, i.e. $(x-y)_i=(x-y)_j$ for each 
$i,j\in\{1,...,|V|\}$. Let $C^+$ be the system (i.e. some elements
 may be repeated several times) defined by
$C^+=(O(G)^Tx;x\in GF[q]^V)$. Let $A_{C^+}(t)=\sum_{i=0}^{|E|} A^+_it^i$,
 where $A^+_i$ equals the number of vectors of $C^+$ with $i$
 non-zero components.
 Then $A_{C^+}(t)=qA_C(t)$.
 
 If $x=(x_1,...,x_{|V|})\in GF[q]^V$ then let
 $l_x$ be the number of different values
 of $x_i$, $i=1,...,|V|$ and let $V^x_1,...,V^x_{l_x}$ be the partition
 of $V$ into $l_x$ non-empty classes such that the components of $x$
 equal in each class.

 Let $cut(x)$ be the $l_x$-cut of $G$ determined by $V^x_1,...,V^x_{l_x}$, 
i.e. the subset of $E$ of the edges with the end-vertices
 in different sets $V^x_i$, $i=1,...,l_x$ and let
 $Cut(x)=(\{V_1,...,V_{l_x}\},cut(x))$.

Each $Cut(x)$ is a $l_x$-cut of $G$ and
 the weight of codeword $O(G)^Tx$ equals
 $|cut(x)|$. 
Let $C^{++}$ be the system defined by
$C^{++}=(cut(x);x\in GF[q]^V)$. Let $A_{C^{++}}(t)=\sum_{W\in C^{++}} t^{|W|}$.
 We have $A_{C^+}(t)=A_{C^{++}}(t)$.

 For $i=1,...,q$ let $X_i=\{x\in GF[q]^V; l_x=i\}$.
 Define an equivalence on $X_i$
 by $x\equiv y$ if $Cut(x)=Cut(y)$. Observe that each equivalence class
 consists of $q(q-1)...(q-i+1)$ elements. Hence 
$$A_{C^{++}}(t)=q+\sum_{i=2}^q q(q-1)...(q-i+1){\cal C}_i(G,(t,...,t)).$$  
This proves the Theorem.

\done
\medskip

We have $C(GF[q],N(G))^*=\{z\in GF[q]^E;O(G)z=0\}$. Hence 
the elements of $C(GF[q],N(G))^*$ are {\it flows} on $G$ with values in $GF[q]$.
 An element of $C(GF[q],N(G))^*$ is called
 {\it nowhere-zero flow} if its weight equals ${|E|}$. Let $F'(G,q)$
 be the subset of $C(GF[q],N(G))^*$ consisting of  nowhere-zero flows.
 $F(G,q)=|F'(G,q)|$ is called {\it flow polynomial} of $G$.

Theorems \ref{d3}, \ref{d4} express a duality between flows and cuts
of a graph. It is a duality of the Tutte polynomial.

Tutte polynomial was defined by Tutte (\cite{Tu1}).
 It may be expressed as a minor
 modification of the Whitney rank generating function (\cite{Wh1}).

\begin{Definition}
Let $G=(V,E)$ be a graph. For $A \subset E$ let $r(A)=|V|-k(A)$,
 where $k(A)$ denotes the number of connected components of $(V,A)$.
 Then let
$$T(G,x,y)=\sum_{A\subset E} (x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)}.$$

$T(G,x,y)$ is called {\it Tutte polynomial} of graph $G$.
\end{Definition}


\medskip

More generally, Tutte polynomial of a matroid (see \cite{Welsh}
 for basic notions of matroid theory) is defined as follows.

\begin{Definition}
Let $M$ be a matroid on set $E$. For $A \subset E$ let $r(A)$
 denote the rank of $A$ in $M$.
 Then let
$$T(M,x,y)=\sum_{A\subset E} (x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)}.$$

$T(M,x,y)$ is called {\it Tutte polynomial} of matroid $M$.
\end{Definition}

For example if $G$ is a graph and $N(G)$ the graphic matroid of $G$
 then $T(G,x,y)=T(N(G),x,y)$.

If $M$ is a matroid and $M^*$ its dual then $r^*(E)-r^*(A)=|A|-r(A)$
and we immediately get
that $T(M,x,y)=T(M^*,y,x)$. This expression is called {\it duality
of the Tutte polynomial}.

\medskip

The following theorem was proved by Green (\cite{Gr}).

\begin{Theorem}
\label{d1}
Let $C$ be a linear code of dimension $k$ and length $n$ over $GF[q]$.
 Then
$$A_C(t)=(1-t)^kt^{n-k}T(M(GF[q],C),(1+(q-1)t)(1-t)^{-1},t^{-1}).$$
\end{Theorem}

As an immediate corollary we get

\begin{Corollary}
\label{d2}
Let $M$ be a matroid represented over $GF[q]$ and let $C(GF[q],M)$ be
 the linear
 code of length $n$ and dimension $k$.
 If $(x-1)(y-1)=q$ then 
$$T(M,x,y)=y^{k-n}(1-y^{-1})^kA_{C(GF[q],M)}(y^{-1}).$$
\end{Corollary}

 By Corollary \ref{d2} and Theorem \ref{d3} we have

\begin{Corollary}
Let $G=(V,E)$ be a graph and let $N(G)$ be the graphic matroid of $G$. 
If $(x-1)(y-1)=2$ then
$$T(G,x,y)=T(N(G),x,y)=y^{|V|-|E|-1}(1-y^{-1})^{|V|-1}[1+{\cal C}_2(G, (y^{-1},...,y^{-1})].$$
\end{Corollary}

\medskip

It follows that the Tutte polynomial of a graph of genus $g$
 may be expressed 
 along the hyperbola $(x-1)(y-1)=2$ as  a linear
 combination of $4^g$ Pfaffians, and hence it may be determined efficiently
 for the graphs embeddable
 on an arbitrary fixed orientable surface.

It is natural to ask whether there is an analogy of this statement for
 binary matroids.

\medskip

Note that Theorem \ref{d3} also follows immediately from Theorem \ref{d1}
 and the
duality of the Tutte polynomial.

\medskip

Finally we make some remarks on the chromatic polynomial and the flow
polynomial of a graph.


\begin{Definition}
 Let $G=(V,E)$ be a graph and $x>1$ an integer.
 Any function $f$ from $V$ to $\{1,...,x\}$ is called {\it $x$-colouring}.
Let $p_i(G,x)$ be the number of proper $x$-colorings of  vertices
 of $G$,
 in which there are $i$ monochromatic edges. Let
$$B(G,x,s)=\sum_{i=0}^{|E|} s^ip_i(G,x).$$
$B(G,x,s)$ is called {\it monochrome polynomial}. $p_0(G,x)$ is called
 {\it chromatic polynomial}.
\end{Definition}

\medskip

Chromatic polynomial was introduced by Birkhoff (\cite{Bir}) and the following
 expression was found by Birkhoff (\cite{Bir}) and Whitney (\cite{Wh1}).

\begin{Theorem}
Let $G=(V,E)$ be a graph. Then $p_0(G,x)=\sum_{H\subset E}(-1)^{|H|} x^{c((V,H))}$,
where $c((V,H))$ denotes the number of the connectivity components of graph
$(V,H)$.
\end{Theorem}


The following Theorem was proved by Tutte (see \cite{Tu2}).

\begin{Theorem}
Let $G=(V,E)$ be a graph. Then
$$p_0(G,k)=(-1)^{|V|-c(G)}k^{c(G)}T(G,1-k,0).$$
\end{Theorem}

\medskip

Using Theorem \ref{c1} we obtain another interesting
 expression for the chromatic
 polynomial. It is a special case of a Lemma on p. 501 of \cite{W4}.

\begin{Theorem}
\label{chr1}
Let $G=(V,E)$ be a  graph and $k>1$. Then 
$$p_0(G,k)=2^{-|E|} \sum_{H\subset E} (-1)^{|H|} U_k((V,H)).$$
\end{Theorem}
\medskip\noindent
{\bf Proof.}
Let $Q_k(z)$ be the polynomial such that 
$$e^{2|E|x}[k+\sum_{i=2}^k i!{k\choose i}{\cal C}_i(G,(e^{-2x},...,e^{-2x}))=
Q_k(e^{2x}).$$

Observe that $p_0(G,k)$ equals to the constant term of $Q_k(z)$. By 
Theorem \ref{c1} we have

$$e^{-|E|x} Q_k(e^{2x})=$$
$$(e^{2x}+1)^{|E|} 2^{-|E|} e^{-|E|x} \sum_{H \subseteq E} [U_k((V,H)) (e^{2x}-1)^
{|H|}(e^{2x}+1)^{-|H|}].$$

Hence 

$$Q_k(e^{2x})=2^{-|E|}\sum_{H\subset E} U_k((V,H)) (e^{2x}-1)^{|H|}(e^{2x}+1)^{|E|-|H|}.$$

It follows that the constant term of $Q_k(z)$ equals to
$$2^{-|E|}\sum_{H\subset E} (-1)^{|H|} U_k((V,H)).$$

\done


The following proposition is straightforward.

\begin{Proposition}
$(-1)^{|H|}U_k((V,H))=B((V,H),k,-1)$.
\end{Proposition}

Hence we get

\begin{Corollary}
Let $G=(V,E)$ be a graph. Then
$p_0(G,k)=2^{-|E|}\sum_{H\subset E} B((V,H),k,-1)$.
\end{Corollary}

\medskip

Nowhere-zero flows are studied extensively. The following theorem was proved
 by Tutte (\cite{Tu2}).

\begin{Theorem}
Let $G=(V,E)$ be a graph and let $q$ be a power of a prime. Then
$$F(G,q)=(-1)^{|V|-|E|-c(G)}T(G,0,1-q).$$
\end{Theorem}

We give an interesting expression for $F(G,q)$ which
 is new as far as we know.

\begin{Theorem}
Let $G=(V,E)$ be a connected graph. Then
$$F(G,q)=q^{-|V|}2^{-|E|}\sum_{A\subset E} U_q((V,A))q^{|A|}(q-2)^{|E|-|A|}.$$
\end{Theorem}
\medskip\noindent
{\bf Proof.}
Let $C=C(GF[q],N(G))$ and
let $D=C(GF[q],N(G))^*$. 
By Theorem \ref{d3} we have
$$A_D(t)=q^{1-|V|}[1+(q-1)t]^{|E|}A_C((1-t)(1+(q-1)t)^{-1}).$$
 From Theorem \ref{d4} and
 Theorem \ref{c1} we get for  $z>0$
$$qA_C(z^{-1})=
q + \sum_{i=2}^q q(q-1)...(q-i+1){\cal C}_i(G,(z^{-1},...,z^{-1}))=$$
$$2^{-|E|}z^{-|E|}\sum_{A\subset E} U_q((V,A))(z-1)^{|A|}(z+1)^{|E|-|A|}.$$

If we let $z=(1+(q-1)t)(1-t)^{-1}$ we get for all $t>0$, $t\neq 1$ 
$$A_D(t)=q^{-|V|}2^{-|E|}\sum_{A\subset E}U_q((V,A))
(qt)^{|A|}(2+(q-2)t)^{|E|-|A|}.$$

It follows that the leading coefficient of $A_D(t)$, which equals $F(G,q)$,
 is equal to
$$q^{-|V|}2^{-|E|}\sum_{A\subset E} U_q((V,A))q^{|A|}(q-2)^{|E|-|A|}.$$

\done



\bibliographystyle{plain}
 
\bibliography{evenbib}

\end{document}

 Then the set of the eulerian subgraphs of $G$ forms the  
 a binary code, and the set of the edge-cuts is its dual code.
 The theorem of Van der Waerden coincides with the above theorem.

Next we introduce the notion of {\it an interaction model}.

We let $\delta(x,y)$ equal to $1$ if $x=y$ and $-1$ otherwise.
\begin{Definition}
Let $G$ be a graph and $A$ a finite set. 
 Let $i(1)$, $i(-1)$ be two non-negative real numbers. For 
$\omega \in A^{V(G)}$ we let
$I(\omega)=\prod_{e=yz\in E(G)} i(\delta(\omega(y),\omega(z))$ and
$Z(A,i,G)=\sum_{\omega \in A^{V(G)}} I(\omega)$. $Z(A,i,G)$ is called
 {\it resonant model}. We also let $A^{V(G)}=\Omega(G,A)$.
\end{Definition}

\medskip

{\bf Example.}
Let $J$ be a real number. Then
$$k! e^{\sum_{f\in E} J}{\cal C}_k(G,(e^{-2J},...,e^{-2J}))=$$
$$\sum_{\sigma \in \{1,...,k\}^V}(\prod_{ij \in E}e^{\delta(\sigma_i\sigma_j)J}=$$
$$Z(A,i,G)$$
where $A=\{1,...,k\} and $i(1)=e^J$ and $i(-1)=e^{-J}$.

\medskip


\begin{Theorem}
Let $(A,i)$ and $(A,g)$ be two resonant models, $i(a)=pg(a)+q$, where
 $a=1,-1$ and $p,q$ are real numbers. Then
$$Z(A,i,G)=q^{|E|}\sum_{S\subset E} p^{|S|}q^{-|S|}Z(A,g,G(S)).$$
\end{Theorem}

\medskip

This theorem again specialises to the theorem of van der Waerden.
 Hence for $F\subset E$, $T(F)=Z(\{1,...,k\},i,F)$ where
 $i(1)=1$ and $i(-1)=-1$.













\begin{Definition}
Let $G$ be a graph and $A$ a finite set.
{\it A flow} is an element of $A^{E(G)}$ such that:  Let $Phi(G,A)=A^E(G)$.

 
\begin{Proposition}
 Let $G=(V,E)$ be a graph and let $x_e=x, e\in E$. Then
$$2^{|E|x} {\cal C}_k(2^{-x},...,2^{-x})= B(G,k,2^x).$$
 \end{Proposition}

\medskip

It is possible to recover the Tutte polynomial from the monochrome
 polynomial (see \cite{w2}).

\begin{Proposition}
$$T(G,x,y)=(y-1)^{-|V|} (x-1) B(G,(x-1)(y-1),y).$$
\end{Proposition}


\begin{Proposition}
$$2^{|E|x}{\cal C}_2(e^{-2x},...,e^{-2x})=(2e^{-x})^{|E|-r(E)}(4sinh(x))^{r(E)}
T(G,coth(x),e^{2x})$$
\end{Proposition}

\begin{Remark}
Hence when $(x-1)(y-1)=k$ then $T(G,x,y)$ may be recovered
 from ${\cal C}_k$. Moreover, when $k=2$, it follows from \ref{c2}
 that $T(G,x,y)$ may be written as a linear combination
 of Pfaffians and thus 
 it may be determined efficiently for all graphs with a bounded genus.

Note that $(coth(x)-1)(e^{2x}-1)=2$.

On the other hand, it is shown by Jaeger, Vertigan and Welsh 
 (see \cite{jvw}) that to
 find $T(G,a,b)$ is number $P$-complete unless $(a-1)(b-1)=1$ or $(a,b)$ is
 one of $9$ special cases. Vertighan proved that
 when restricted to planar graphs,
 one more case is efficiently solvable, the case $(a-1)(b-1)=2$.

 Tutte polynomial of a matroid is defined as well (see \cite{w2}).

When $(x-1)(y-1)=k$ and $M$ is a matroid representable
 over $F^k$ then $T(M,x,y)$ specialises
 to the weight enumerator of the corresponding linear code over $F^k$. 
 This suggests that each weight enumerator of a binary code may
 be equal to some nice function of determinants as well.
 This question is considered in the continuation of the present paper.
\end{Remark}



\bibliographystyle{plain}
 
\bibliography{evenbib}

\end{document}


\section{The Algorithmic Complexity.}

Let us summarize first the results of the previous sections
from an algorithmic point of view.

\begin{Theorem}
Let $S$ be a fixed surface and $k$ a fixed positive integer.
Let $G=(V,E)$ be a graph drawn on $S$ and let the variables
$x_e;e\in E$ be partitioned into at most $k$ classes. Then
${\cal P}(G,x)$, ${\cal E}(G)$, ${\cal C}_2(G)$ may be determined 
efficiently. Also, it is possible to verify efficiently
 whether $G$ is Pfaffian.
\end{Theorem}

\medskip

Next we include two negative results of F. Barahona (see \cite{b}).

A planar rectangular grid will be called {\it $1$-grid},
and in general a rectangular grid with $k$ levels in the third
 coordinate will be called {\it $k$-grid}.
A graph which becomes planar after deleting one vertex is called
 {\it apex graph}.

\medskip

\begin{Theorem}
Let $G$ be a $2$-grid and let $x_e \in \{0,1,-1\}$ for each edge $e$
 of $G$. Then the problem to find the edge-cut of $G$ of
 minimum total weight is an NP-complete problem.
\end{Theorem}


Next we include three results of M. Jerrum and A. Sinclair (see \cite{js}).


\begin{Theorem}
\label{a1}
There exists a fpras (fully polynomial approximation scheme) for 
 ${\cal C}_2(G)$ in any  nonnegative rational vector $(x_e; e\in E(G))$.
\end{Theorem}

\medskip

The same result should hold for ${\cal E}(G)$.

\medskip


\begin{Theorem}
\label{a2}
There is no fpras for 
 ${\cal C}_2(G)$ in  $0,1,-1$ vectors $(x_e; e\in E(G))$, even when
 $G$ is a $2$-grid.
\end{Theorem}

\begin{Theorem}
\label{a3}
To determine ${\cal C}_2(G)$ is number $P$ complete even when all non-zero
  $x_e$ equal to  the same positive rational number.
\end{Theorem}

\medskip

\begin{Remark}
The same result as \ref{a3} holds for ${\cal E}(G)$.

It may be interesting to see whether the Lagrange interpolation
 may be used to approximate the size of a maximum cut.

What is known about the complexity of (approximating) ${\cal C}_k(G)$,
$k>2$?
\end{Remark}

\medskip

M. Jerrum and A. Sinclair also proved (see \cite{js}).

\begin{Theorem}
There exists a fpras for ${\cal P}(G,x)$ when each $x_e$ equals to the same
 non-negative rational number and $G$ is a dense graph.
\end{Theorem}

It is number $P$ complete to determine the number of perfect matchings
 of (bipartite) graphs, i.e. ${\cal P}(G,x)$ when $x_e=1, e\in E(G)$ 
 (see \cite{Val}). This task for bipartite graphs is equivalent to determining
 permanents of $0,1$ matrices.

It follows from the results of this paper that the number of perfect
 matchings may be determined efficiently for graphs with a bounded
 genus. May the same result hold for any class of graphs with a forbidden
 minor? The answer to this question may be negative, as the following
 proposition suggest.

\begin{Proposition}
It is NP-complete to determine ${\cal P}(G,x)$ even when $G$ doesnot
 have a $K_8$ minor, and the variables $x_e; e\in E$ are partitioned into
 two classes.
\end{Proposition}
\medskip\noindent
{\bf Proof.}
It follows from \ref{ap} and \ref{c2} that it is NP-complete to determine
 ${\cal E}(G)$ for apex graphs. Applying the construction of Fisher
 to an apex graph, we get a graph with no $K_8$ minor.

\done

\bigskip

{\bf Cocluding Remarks.}
In a continuation of this paper which is in preparation
  we consider the following related
 problems: 
\begin{enumerate}
\item[1.] The weight enumerator of a binary code,
\item[2.] The drawing of grids and the 
 use of the proposed method to find closed forms of the
   Ising problem for some lattices,
\item [3.] The drawing of complete bipartite graphs and the use of the 
 proposed method for proving some permanent inequalities.
\end{enumerate}

\bigskip
\noindent{\bf Acknowledgements.} The   authors are grateful to 
 Robin Thomas and Dominic Welsh for fruitful discussions.








\bibliographystyle{siam}
\begin{thebibliography}{1}

\bibitem{Val}
{\sc L.G. Valiant.}
{\em The Complexity of Computing the Permanent.}
Theor. Comp. Sci. 47, 1986, 85-93.

\bibitem{lp}
{\sc L.~Lov\'asz and M.~Plummer}. {\em Matching Theory}, vol.~29 of {\em Annals of
  Discrete Mathematics}, North-Holland, 1986.



\bibitem{o}
{\sc J.~Oxley}. {\em Matroid Theory}.
Oxford University Press, 1992.

\bibitem{jvw}
{\sc F. Jaeger, D. L. Vertigan, D.J.A. Welsh.}
{\em On the Computational Complexity of Jones and Tutte Polynomials.}
Math. Proc. Camb. Phil. Soc. 108, 1990, 35-53.


\bibitem{w1}
{\sc    D.J.A. Welsh.}
   {\em Matroid Theory}.
   Academic Press, London,  1976.

\bibitem{w2}
{\sc    D.J.A. Welsh.}
   {\em Complexity: Knots, Colourings and Counting}.
   London Mathematical Society Lecture Note Series 186,
   Cambridge University Press 1993.

\bibitem{f}
{\sc M.E. Fisher.}
{\em On the Dimer Solution of Planar Ising Models.}
Journal of Mathematical Physics 7, 10, 1966.

\bibitem{k1}
{\sc P.W. Kasteleyn.}
{\em The Statistics of Dimers on a Lattice.}
Physica 27, 1961.

\bibitem{k2}
{\sc P.W. Kasteleyn.}
{\em The Statistics and Phase Transitions.}
Journal of Mathematical Physics 4, 2  1963.


\bibitem{k3}
{\sc P.W. Kasteleyn.}
{\em Graph Theory and Crystal Physics.}
 Graph Theory and Theoretical Physics, ed. F. Harary
 London, Academic Press 1967, 43-110.

\bibitem{b}
{\sc F. Barahona.}
{\em On the Computational Complexity of Ising Spin Glass Models.}
J. Phys. A 15, 1982.

\bibitem{js}
{\sc M. Jerrum, A. Sinclair.}
{\em Polynomial-Time Approximation Algorithms For the Ising Model.}
SIAM J. Computing 22, 5  1993.

\bibitem{GH}
{\sc O. Goldschmidt, D. S. Hochbaum.}
{\em A Polynomial Algorithm For the $k$-Cut Problem For Fixed $k$.}
Mathematics of Operations Research 19, 1, 1994, 24-37.

\bibitem{DJPSY}
{\sc Dalhaus et.al.}
{\em The Complexity of the Multiway Cuts. Extended Abstract.}
Proc. 1992 ACM Symposium on Theory of Computing, 241-251.


        

\end{thebibliography}


\end{document}

\end{document}

\documentstyle[12pt,fleqn]{article}

%Definizioni Latex Anna 

\newtheorem{Definition}{\bf Definition}[section]
\newtheorem{Example}[Definition]{\bf Example}
\newtheorem{Remark}[Definition]{\bf Remark}
\newtheorem{Lemma}[Definition]{\bf Lemma}
\newtheorem{Theorem}[Definition]{\bf Theorem}
\newtheorem{Corollary}[Definition]{\bf Corollary}
\newtheorem{Proposition}[Definition]{\bf Proposition}

\textwidth 15.6 cm   %**************
\textheight 20 cm  %**************
\oddsidemargin 0.4 cm  %**************
\topmargin 0.6 cm  %**************

\newcommand{\bform}{\begin{displaymath}}
\newcommand{\eform}{\end{displaymath}\smallskip}
\newcommand{\beqn}[1]{\begin{equation}\label{#1}}
\newcommand{\eeqn}{\end{equation}\smallskip}
\newcommand{\beqna}[1]{\begin{eqnarray}\label{#1}}
\newcommand{\eeqna}{\end{eqnarray}\smallskip}
\newcommand{\beqnan}{\begin{eqnarray*}}
\newcommand{\eeqnan}{\end{eqnarray*}\smallskip}
\newcommand{\tr}[1]{#1^{\scriptscriptstyle T}}
\newcommand{\rif}[1]{(\ref{#1})}
\newcommand{\vect}[2]{\left(\begin{array}{c} #1\\#2 \end{array}\right)}
\newcommand{\done}{\hfill$\Box$\par}

\def\Re{I\!\!R}
\def\gt{>}
\def\lt{<}
\def\sp{\;\;}
\def\wug{=^{\!\!\!\!\!^{2}}}
\def\wnug{\ne^{\!\!\!\!\!^{2}}}
\def\prec{<^{\!\!\!\!\!^{L}}}
\def\prece{\le^{\!\!\!\!\!^{L}}}


%Fine Definizioni Latex Anna 

\begin{document}






