% Second paper on Pfaffians, revised version
% accepted on Elec. J. Comb. 
%sent June 98

\documentclass[12pt,fleqn]{article}
\usepackage{latexsym}

%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.2 cm   %**************
\textheight 229 mm  %**************
\oddsidemargin 0 cm  %**************
\topmargin -\headheight  %**************

\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}}}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 6 (1999), \#R7\hfill}

\begin{document}


\begin{titlepage}
\thispagestyle{empty}
\title{\large {\bf On the Theory Of Pfaffian Orientations.}\\
{\bf II. $T$-joins, $k$-Cuts, and Duality of Enumeration. }} 




\author{
\thanks {Supported by NATO-CNR Fellowship}
       \normalsize {\bf Anna Galluccio}\\
       {\normalsize Istituto di Analisi dei Sistemi ed} \\
       {\normalsize Informatica - CNR}\\ 
       {\normalsize viale Manzoni 30}\\
       {\normalsize 00185 Roma}\\
        {\normalsize ITALY}\\
       {\normalsize galluccio@iasi.rm.cnr.it}
\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}\\
   {\normalsize 118 00 Praha 1}\\
   %{\normalsize and University of Waterloo }\\
   {\normalsize CZECH REPUBLIC}\\
   {\normalsize loebl@kam.ms.mff.cuni.cz}
}

\date{}
\maketitle

\begin{center}
Received February 18, 1998; Accepted May 22, 1998.
\end{center}
\bigskip

\begin{abstract}
This is a continuation of our paper ``A Theory of Pfaffian Orientations I: 
Perfect Matchings and Permanents".
We present a new combinatorial way to compute the generating
 functions of $T$-joins and $k$-cuts of graphs.
 As a consequence, we show that the computational problem
 to find the maximum weight of an edge-cut is polynomially
 solvable for the instances $(G,w)$ where $G$ is a graph
 embedded on an arbitrary
 fixed orientable surface and the weight function $w$ 
 has only a bounded number
 of different values. We also survey the 
 related results concerning a duality of the Tutte polynomial, and present
 an application for the weight enumerator of a binary code.
 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}

\bigskip
\begin{center}
{\bf Mathematical Reviews Subject Numbers} 05B35, 05C15, 05A15
\end{center}

\end{titlepage}

\section{Introduction}
This is a continuation of our paper ``A Theory of Pfaffian Orientations I: 
Perfect Matchings and Permanents".
 We present a new combinatorial way to compute the generating
 functions of $T$-joins and $k$-cuts of graphs.

 A graph is a pair $G=(V,E)$ where $V$ is a set and $E$ is a set
 of unordered pairs of elements of $V$. The elements of $V$ are called 
{\it vertices} and those of $E$ are called {\it edges}. If $e=xy$ is an 
edge then $x,y$ are called endvertices of $e$.

 In this paper $V$ will 
always  be finite, $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)$ denote the 
vector whose components are indexed by the edges of $G$ and, 
for $M\subset E$, we let $x(M)$ denote the product of the variables of 
the edges of $M$.

A graph $(V',E')$ is called a {\it subgraph} of graph $G=(V,E)$ if
 $V'\subset V$ and $E'\subset E$.
A {\it perfect matching} of a graph is a set of pairwise disjoint edges,
 whose union equals the set of the vertices.

Let $P= v_1,e_1,v_2,e_2,...,v_i,e_i,v_{i+1},...,e_n,v_{n+1}$ be a sequence
 such that each $v_j$ is a vertex of a graph $G$, each $e_j=v_jv_{j+1}$ is 
an edge of $G$, and $v_i\neq v_j$ for $i<j$ except if
 $i=1$ and $j=n+1$. If also $v_1\neq v_{n+1}$ then $P$ is called {\it a path}
 of $G$. If $v_1=v_{n+1}$ then $P$ is called a {\it cycle} of $G$.
 In both cases the {\it length} of $P$ equals $n$.

 The graph $G=(V,E)$ is {\it connected} if any pair of vertices is joined 
 by a path, and it is called {\it $2$-connected} 
 if the graph $G_v=(V-\{v\},\{e\in E; v\notin e\})$ is connected for each 
vertex $v$ of $G$. Each maximal $2$-connected subgraph of $G$ is called
 a {\it $2$-connected component} of $G$. 


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

\medskip
A subgraph $G'=(V,E')$ of a graph $G=(V,E)$ is called {\it eulerian}
 if the degree of each vertex of $G'$ is even.

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

Let $G=(V,E)$ be a graph and $T\subset V$. {\it A $T$-join} is a subgraph
$G'=(V,E')$ such that the degree of a vertex $v$
 of $G'$ is odd if and only if $v\in T$. Eulerian subgraphs 
 are $T$-joins when $T=\emptyset$.


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

\medskip
Next we consider $k$-cuts.

\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 endvertices in different parts $V_i$, $i=1,...,k$.
\end{Definition}


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


\medskip
An {\it embedding} of a graph on a surface is defined in a natural way:
 the vertices are embedded as points, and each edge is embedded as a
 continuous non-self-intersecting curve connecting the embeddings
 of its endvertices. The interiors of the embeddings of the edges
 are pairwise disjoint and the interiors of the curves embedding edges
do not contain points embedding vertices. 

The {\it genus} $g$ of a graph $G$ is that of the orientable surface  
${\cal S}\subset \Re^3$ of minimal genus on which $G$ may be embedded.
 
\medskip 

The following theorem is the main result of \cite{GL6}.


\begin{Theorem}
\label{gen1}
Let $G$ be a graph of genus $g$.
 Then ${\cal P}(G,x)$
may be expressed as a linear combination of $4^g$ square roots of 
determinants.
\end{Theorem}




\section{$T$-joins.}

There are several ways of relating the problem of counting eulerian 
subgraphs and the problem of counting perfect matchings. Each method 
involves replacing each vertex of a given graph by a cluster of vertices 
in a new ``counting'' graph.
One of these methods turns out to be more appropriate
 for our purposes since it 
preserves the genus of the original graph. It was originally proposed by Fisher 
(see \cite{Fish}) for counting the number of eulerian subgraphs of a 
graph. Here we extend his construction in order to solve the
more general problem of counting the number of $T$-joins of a graph.

The construction may be performed in polynomial time and hence, 
together with Theorem \ref{gen1}, 
 yields an algorithm to compute ${\cal T}_T(G,x)$. 

 Other constructions leading to the same result are useful in the study
 of crystal structures. We will discuss them in greater detail in a 
forthcoming paper.



\begin{Definition}
Let $G=(V,E)$ be a graph and let $v\in V$. Let $e_1,...,e_k$ be an ordering
of the edges of $G$ incident with $v$. The {\it even splitting} of $v$
is a graph $G'=(V',E')$ such that $V'=V-\{v\} \cup \{v_1,...,v_{6k}\}$, 
and $E'=E-\{e_1,...,e_k\} \cup \{e'_1,...,e'_k\} \cup \{v_tv_{t+1}; 
0<t<6k\} \cup \{v_{3j+1}v_{3j+3}; j=0,...,2k-1\}$ where $e'_i$ is 
obtained from
$e_i$ by replacing $v$ by $v_{6(i-1)+2}$, $i=1,\dots,k$. 
We say that $e'_i$ is the image of $e_i$ in $G'$.

The {\it odd splitting} of $v$ is obtained from the even splitting of $v$
 by deleting vertices $v_{6k}$, $v_{6k-1}$, $v_{6k-2}$.
\end{Definition}


\begin{Definition}
Let $G=(V,E)$ be a graph and $T\subset V$. 
We denote by $G_s=(V_s,E_s)$ the graph
 obtained from $G$ 
by odd splitting of all  vertices of $T$ and even splitting of all
 vertices of $V-T$. If the edge $f'$ of $G_s$
 is the image of the edge $f$ of $G$ then we let
 $x^s_{f'}=x_f$. We let $x^s_e=1$ for the remaining
 edges $e$ of $G_s$.
\end{Definition}


\begin{Theorem}
\label{f}
 Let $G$ be embeddable on 
 an orientable surface ${\cal S}$ and let each even and odd splitting
 of a vertex be performed in the clockwise order of the embeddings
 of its incident edges. Then $G_s$ is also embeddable on ${\cal S}$.
 Moreover ${\cal P}(G_s,x^s)={\cal T}_T(G,x)$.  
\end{Theorem}

{\bf Proof.} The first statement follows from the definition of even and 
odd splitting. Next, observe that the
$T$-joins $W$ of $G$ are in one-to-one correspondence with the perfect 
matchings $P_W$ of $G_s$. Note that $P_W$ contains the set of the images of 
the edges of $W$. This together with the choice of $x^s$ implies that 
$x(W)=x^s(P_W)$, for each $T$-join $W$, and the theorem follows.
\done



\section{$k$-cuts.}

In this section we consider the generating function of the multicuts of a graph
 and we 
derive an important relation between it and the generating function of
the eulerian subgraphs of the same graph.
 It is well known that for a planar graph $G$,
the cuts of $G$ are in one-to-one correspondence with the eulerian 
subgraphs of its geometric dual $G^*$.
This correspondence does not hold anymore for graphs embeddable on 
surfaces of genus greater than zero; 
in these cases we need a more general duality result, due to  
van der Waerden (see \cite{vdW}, \cite{w2}, \cite{KAST1}). 

We use the following notation:

$$sinh(z,x)={{z^x-z^{-x}}\over {2}},\quad cosh(z,x)={{z^x + z^{-x}}\over 
{2}}, \quad th(z,x)={{sinh(z,x)}\over {cosh(z,x)}}.$$

Note that $sinh(x)=sinh(e,x)$ and $cosh(x)=cosh(e,x)$.

Given a graph $G=(V,E)$, we denote by $\sigma\in \{1,\dots,k\}^{V}$
a $|V|$-dimensional vector whose components $\sigma_i$, $i=1,\dots,|V|$, 
take values in the set $\{1,\dots,k\}$.
Clearly, any such vector identifies a partition of $V$ into $i \leq k$
disjoint sets and, consequently, an $i$-cut of $G$.

Let us denote by $\delta$ the vector indexed by the edges of $G$ whose 
component $\delta_{ij}=\delta(\sigma_i\sigma_j)$, $ij\in E$, equals 
$1$ if  $\sigma_i=\sigma_j$ and $-1$ otherwise.
 
Moreover, for any $A\subset E$ 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, $z$ a variable and $k>1$. Then
$$z^{\sum_{f\in E} x_f}[k+\sum_{i=2}^k i!{k\choose i}{\cal 
C}_i(G,(z^{-2x_f}:f\in E))]=$$

$$(\prod_{f \in E} cosh(z,x_f)) \sum_{A \subseteq E}
U_k((V,A))\prod_{f \in A}th(z,x_f).$$
\end{Theorem}

\medskip\noindent
{\bf Proof.}
Using the identity
 
$$z^{x\delta(\sigma_i\sigma_j)}=cosh(z,x)+\delta(\sigma_i\sigma_j)sinh(z,x)$$


the result follows after some algebraic manipulations. In fact,

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

\bigskip
where $\prod_{ij\in A}\delta(\sigma_i\sigma_j) th(z,x_{ij})=1$ if 
$A=\emptyset$. 
Hence, the theorem follows.
\done

\bigskip
Specializing the above result to the case of edge-cuts, i.e. $k=2$, we 
obtain the following result:
\begin{Theorem}
\label{c2}
 Let $G$ be a graph, $z$ a variable
 and let ${\cal C}'_2(G,x)={\cal C}_2(G,x)+1$.
 Then
$$2z^{\sum_{f\in E} x_f}{\cal C}'_2(G,(z^{-2x_f}: f \in E))=
(\prod_{f \in E} cosh(z,x_f)) 2^{|V|} {\cal E}(G,(th(z,x_f): f\in E)).$$
\end{Theorem}
\medskip\noindent
{\bf Proof.} We have, from Theorem \ref{c1}, that
$$2z^{\sum_{f\in E} x_f}{\cal C}'_2(G,(z^{-2x_f}: f \in E))=
(\prod_{f \in E} cosh(z,x_f)) \sum_{A \subseteq E}
U_2((V,A))\prod_{f \in A}th(z,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 $k$ be a positive integer.
Let ${\cal G}$ be the class of graphs $G=(V,E)$ such that 
 the edges are partitioned into at most $k$ classes
and the variables $x_e$ are equal in each class.

 Then there is a polynomial algorithm which,
given $G \in {\cal G}$ and ${\cal E}(G,x)$ as input, produces ${\cal 
C}_2(G,x)$.
\end{Theorem}
\medskip\noindent
{\bf Proof.}
By Theorem~\ref{c2}, we have that   
$$\prod_{f \in E} cosh(z,x_f) 2^{|V|} {\cal E}(G,(th(z,x_f): f\in E))=$$

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


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

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

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

Observe that $\prod_{f\in E} z^{-2x_f} {\cal E}^*(z^{2x_f}: f\in E))$ is 
a polynomial $Q(z^{-2x_f}:f\in E)$ in the functions $z^{-2x_f}$ and 
hence, its nonzero monomials correspond uniquely to nonzero terms of 
${\cal C}'_2(G,z^{-2x_f}:f\in E)$.

It follows that, given $G \in {\cal G}$ and ${\cal E}(G,x)$, the polynomial
 ${\cal E}^*(G,x)$ and, consequently, ${\cal C}_2(G,x)$ may be expressed 
in polynomial time. 

\done

\medskip
It immediately follows from Theorem~\ref{c3}, 
Theorem~\ref{f} and Theorem \ref{gen1} that  it is
 possible to find efficiently the maximum weight of an edge-cut
 for the graphs $G=(V,E)$ embeddable on an arbitrary fixed orientable 
surface, which have only a bounded number of different edge-weights.

Using similar arguments we can obtain a polynomial time algorithm 
 when the weights are integers bounded in  absolute value 
 by a polynomial of the size of the graph. The details of these 
 algorithms will appear elsewhere.


%It was pointed to us in the Dagstuhl seminar in December 1997 by Martin
% Groetschel that this implies, using Corollary
 %$6.2.19$ of \cite{GLS}, that the general max-cut problem is polynomially
 %solvable for the graphs embeddable on an arbitrary fixed orientable 
%surface,

%\begin{Theorem}
%\label{algo}
%Let ${\cal S}$ be an orientable surface. 
%Let ${\cal G_S}$ be the class of graphs $G=(V,E)$ which may be 
%embedded on ${\cal S}$. Then it is
% possible to find efficiently the maximum weight of an edge-cut
% for the graphs of ${\cal G_S}$.
%\end{Theorem}




\section{A Duality of Enumeration.}

We will show now how the duality result proved in the previous 
section leads to interesting expressions for well-known polynomials 
studied in combinatorics.

We start by considering the {\it Tutte polynomial}; 
it has been defined by Tutte (\cite{Tu1}) and it may be expressed as a 
minor modification of the Whitney rank generating function (\cite{Wh1}).

\begin{Definition}
Let $G=(V,E)$ be a connected graph. For $A \subset E$ let $r(A)=|V|-c(A)$,
 where $c(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 the {\it Tutte polynomial} of graph $G$.
\end{Definition}


\medskip

More generally, the 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 the {\it Tutte polynomial} of matroid $M$.
\end{Definition}

\medskip
For example if $G$ is a graph and ${\cal N}_G$ the graphic matroid of $G$
 then $T(G,x,y)=T({\cal 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 relation is called {\it 
duality of the Tutte polynomial}.

\bigskip\noindent
\subsection{\bf Weight enumerator of a linear code.}

Let $V= {\bf F}^n$ be a vector space  over a field ${\bf F}$.
 Each subspace $C$ of $V$ of dimension $k$ is called a 
 {\it linear code of length $n$ and dimension $k$}.
The elements of a linear code are called {\it codewords}.
The {\it weight} of a codeword is the number of its nonzero entries.
The {\it weight distribution} of $C$ is the sequence $A_0,A_1,\dots,A_n$ 
where $A_i$ equals the number of codewords of $C$ of weight $i$, $0\le 
i\le n$. 

The {\it dual code} of $C$ is denoted by $C^*$ and consists of all those 
$n$-tuples $(d_1,\dots,d_n)$ of ${\bf F}^n$ satisfying 
$$c_1d_1+\dots+c_nd_n=0$$

\noindent
for all codewords $(c_1,\dots,c_n)\in C$.
Hence, $C^*$ is a code of length $n$ and dimension $n-k$.

The {\it weight enumerator} of $C$ is the polynomial

$$A_C(t)=\sum_{i=0}^n A_it^i.$$
 
\medskip
The following theorem was proved by MacWilliams (\cite{mac}) and it 
states a fundamental relation between the weight enumerators of $C$ and 
of its dual $C^*$. 

\begin{Theorem}
\label{d3}
Let $C$ be a linear code of length $n$ and dimension $k$ over $GF[q]$ and
$1+(q-1)t \neq 0$. Then
$$A_{C^*}(t)=\frac{[1+(q-1)t]^n}{q^{k}}A_C(\frac{(1-t)}{1+(q-1)t}).$$
\end{Theorem}

\medskip
If the linear code of length $n$ is given as
 the row space of a $k\times n$ matrix $A$ over a field ${\bf F}$, i.e. 
 $C=\{A^Tx;x\in {\bf F}^k\}$, then we will denote it as $C({\bf F},A)$.
Moreover, if a matroid $M$ is 
 represented by the columns of $A$, then we let $M=
 M({\bf F},C)$ and $C=C({\bf F},M)$.
 In this case we have  $C^*=\{x\in {\bf F}^n; Ax=0\}$.
% We have $M({\bf F},C^*)=M({\bf F},C)^*$.


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

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

\medskip
Note that Theorem \ref{d3} also follows immediately from Theorem \ref{d1}
and the duality of the Tutte polynomial.
 As an immediate corollary we get

\begin{Corollary}
\label{d2}
Let $M$ be a matroid represented over $GF[q]$.
 If $(x-1)(y-1)=q$ and $0\neq y \neq 1$ then 
$$T(M,x,y)=y^n(y-1)^{-k}A_{C(GF[q],M)}(y^{-1}).$$
\end{Corollary}


Consider now the following example.
Let $G=(V,E)$ be a graph and let ${\cal N}_G$ be the graphic matroid 
of $G$.
Let $O_G$ be an oriented incidence matrix of $G$, i.e. an $|V|\times |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
 ${\cal N}_G$ over an arbitrary field ${\bf F}$.

 The set of the characteristic vectors of $2$-cuts of a graph $G$ 
 (including the empty cut) equals $C(GF[2],{\cal N}_G)$ and
 the set of the characteristic vectors of eulerian subgraphs of $G$
 equals  $C(GF[2],{\cal N}_G)^*$. 
 Using this terminology, it may be checked easily that
 Theorem \ref{d3} generalizes Theorem \ref{c2}.

\medskip

\begin{Theorem}
\label{d4}
Let $G=(V,E)$ be a connected graph. Then
$$A_{C(GF[q],{\cal 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],{\cal 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 (in contrast with
 {\it a set}, some elements of a system may appear 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.
 Since each equivalence class of $\equiv$ consists of $q$ elements
 we have  $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$
 are equal in each class.

 Let $cut(x)$ be 
the subset of $E$ formed by those edges having endvertices
 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 an $l_x$-cut of $G$ and
 the weight of the 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
 of $\equiv ^*$ consists of $q(q-1)...(q-i+1)$ elements. Hence 
$$qA_C(t)=A_{C^+}(t)=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

\bigskip
By Corollary \ref{d2} and Theorem \ref{d4} we have

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

\bigskip
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.

\bigskip\noindent
\subsection{\bf Flow polynomial of graphs.}

We have $C(GF[q],{\cal N}_G)^*=\{z\in GF[q]^E;O_Gz=0\}$.
The elements of $C(GF[q],{\cal N}_G)^*$ are {\it flows} on $G$ with values 
in $GF[q]$. 
 An element of $C(GF[q],{\cal N}_G)^*$ is called
 a {\it nowhere-zero flow} if its weight equals ${|E|}$. Let $F'(G,q)$
 be the subset of $C(GF[q],{\cal N}_G)^*$ consisting of  nowhere-zero 
flows.
 $F(G,q)=|F'(G,q)|$ is called the {\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.

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}

\bigskip
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 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],{\cal N}_G)$ and let $D=C(GF[q],{\cal 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

%\medskip

%{\bf Acknowledgement.} We would like to thank to Martin Groetschel for 
%pointing to us that Corollary $6.2.19$ of \cite{GLS} completes the proof
% of Theorem \ref{algo}.

\medskip
\bibliographystyle{plain}
 
\bibliography{evenbib}

\end{document}





@book{GareyJohnson,
 author = "Michael R. Garey and David S. Johnson",
 title = "Computers and Intractability",
 publisher = "W. H. Freeman and Company",
 year = "1979",
 address = "New York"
}

@book{algalg,
 author = "Chee Keng Yap",
 title = "Fundamental Problems in Algorithmic Algebra",
 publisher = "Princeton University Press",
 year = "1993",
 address = "Princeton"
}


@book{Schr2,
 author={A. Schrijver},
 title={Theory of Linear Programming and Integer Programming},
 publisher={John Wiley \& Sons},
 year={1986},
 address={New York}
}


@book{Tru, 
 author = {K. Truemper}, 
 title = {Matroid Decomposition},
 publisher ={Academic Press},
 year = {1992},
 address = {San Diego, CA}
}

@book{Welsh, 
 author = {D. J. A. Welsh}, 
 title = {Matroid Theory}, 
 publisher ={Academic Press},
 year = {1976},
 address = {London} 
}


@inproceedings{BS,
 author= {R. A. Brualdi and  B. L. Shader}, 
 title= {On sign-nonsingular matrices and the conversion of the 
        permanent into the determinant},
 booktitle={Applied Geometry and Discrete Mathematics}, 
 year={1991},
 publisher={American Math. Society},
 address={Providence},
 pages={117-134}
} 
 
 @book{algophys,
 author= {M. Junger, G. Reinelt, H. Rieger, G. Rinaldi}, 
 title= {Algorithmic Techniques in Physics}, 
 publisher={Dagstuhl-Seminar-Report 197},
 year={1997},
address={Dagstuhl}
}

@inproceedings{LI1,
 author = {C. H. C. Little},
 title = {An extension of {K}asteleyn's method of enumerating the 1-factors
          of planar graphs},
 booktitle = {Combinatorial Mathematics, Proceedings 2nd Australian Conference},
 year = {1974},
 publisher = {Springer},
 address = {Berlin},
 series = {Lecture Notes in Mathematics},
 volume = {403}
}

@inproceedings{Kast,
 author = {P.W. Kasteleyn},
 title = {Graph theory and crystal physics}, 
 booktitle = {Graph theory and theoretical physics },
 year = {1967},
 publisher = {Academic Press},
 address = {New York}
}


@inproceedings{LO2,
 author = {L. Lov\'asz},
 title = {Problem 2},
 booktitle = {Recent advances in graph theory, Proceedings Symposium Prague},
 year = {1975},
 publisher = {Academia},
 address = {Praha}
}
 

@article{AL,
 author={N. Alon and N. Linial},
 title={Cycles of length 0 mod k in directed graphs},
 journal={J. Combin. Theory B},
 volume={47},
 year={1989},
 pages={114-119}
}
 
@article{Wh1,
 author={H. Whitney},
 title={A Logical Expansion in Mathematics},
 journal={Bull. Amer. Math. Soc.},
 volume={38},
 year={1932},
 pages={572-579}
}

@article{Bir,
 author={Birkhoff},
 title={A determinant formula for the number of ways of colouring a map},
 journal={Annals of Mathematics},
 volume={14},
 year={1912},
 pages={42-46}
}

@article{Gr,
 author={C. Greene},
 title={Weight Enumeration and the Geometry of Linear Codes},
 journal={Studies in Applied Mathematics},
 volume={55},
 year={1976},
 pages={119-128}
}

@article{vdW,
 author={B.L. van der Waerden},
 title={Die lange Reichweite der regelmassigen Atomanordnung in Mischkristallen},
 journal={Z. Physik},
 volume={118},
 year={1941},
 pages={473}
}

@article{Tu1,
 author={W.T. Tutte},
 title={ A ring in graph theory},
 journal={Proc. Camb. Phil. Soc.},
 volume={43},
 year={1947},
 pages={26-40}
}

@article{Tu2,
 author={W.T. Tutte},
 title={ A contribution to the theory of chromatic polynomials},
 journal={Canad. J. Math.},
 volume={6},
 year={1954},
 pages={80-91}
}

@article{mac,
 author={J. MacWilliams},
 title={A theorem on the distribution of weights in a systematic code},
 journal={Bell Syst. Tech. J.},
 volume={42},
 year={1962},
 pages={654}
}

@article{APY,
 author={E. M. Arkin and C. H. Papadimitriou and M. Yannakakis},
 title ={Modularity of cycles and paths in graphs}, 
 journal = {J. ACM}, 
 volume = {38},
 year = {1980},
 pages = {255-274}
}

@article{B1,
 author= {F. Barahona},
 title= { On the Computational Complexity of Ising Spin Glass Models},
 journal={J. Phys. A},
 volume={15}, 
 year= {1982},
 pages={   }
}

@article{B2,
 author= {F. Barahona},
 title= { Balancing Signed Toroidal Graphs in Polynomial Time},
 journal={Preprint University of Chile},
 volume={}, 
 year= {1983},
 pages={   },
 note= {Unpublished manuscript}
}


@article{BGJR,
 author= {F. Barahona and M. Gr\"otschel and M. J\"unger and G. Reinelt},
 title= {An application of combinatorial optimization to statistical physics 
         and circuit layout design},
 journal={Operations Research},
 volume={36}, 
 year= {1988},
 pages={493-513}
}


@article{DJRR,
 author= {M. J\"unger and G. Reinelt and G. Rinaldi},
 title= {An application of combinatorial optimization to statistical physics 
         and circuit layout design},
 journal={Operations Research},
 volume={36}, 
 year= {1988},
 pages={493-513}
}


@article{godsil,
 author= {C. Godsil},
 title= {Matroids, Codes and Physics},
 journal={Manuscript},
 volume={}, 
 year= {1997},
 pages={   }
}

@article{GW,
 author= {M. X. Goemans and D. P. Williamson}, 
 title= {Improved approximation algorithms for maximum cut and 
         satisfiability problems using semidefinite programming}, 
 journal={J. of ACM}, 
 volume= {42},
 year= {1995}, 
 pages={1115-1145}
}


@article{Cayley,
 author= {A. Cayley}, 
 title= {Sur les determinants gauches}, 
 journal={Crelle's J.}, 
 volume= {38},
 year= {1847}, 
 pages={93-96}
}

@article{CGK,
 title={Even cycles in directed graphs},
 author={F.~R.~.K. Chung and W. Goddard and D. J. Kleitman},
 journal={Siam J. Discrete Math.},
 volume={7},
 year={1994},
 pages={474-483}
}

@article{Cunn, 
 author={W. Cunningham}, 
 title={ Chords and disjoint paths in matroids}, 
 journal={Discr. Math.},
 volume={19},
 year={1977},
 pages={7-15} 
}


@article{DP,
 author= {C. Delorme and S. Poljak},
 title= {Laplacian eigenvalues and the maximum cut problem},
 journal={Math. Prog.},
 volume={62}, 
 year= {1993},
 pages={557-574}
}

 
@article{FHW, 
 author = {S. Fortune and J. E. Hopcroft and J. Wyllie}, 
 title = {The directed subgraph homeomorphism}, 
 journal = {Theor. Comput. Sci.}, 
 volume = {10},
 year = {1980},
 pages = {111-121}
}
 
@article{Fried,
 author= {S. Friedland},
 title= {Every 7-regular digraph contains an even cycle},
 journal = {J. Comb. Th. B},
 volume={46},
 year={1989},
 pages={249-252}
}

@article{JS1, 
 author={M. Jerrum and A. Sinclair}, 
 title = {Approximating the permanent}, 
 journal = {SIAM J. Comp.}, 
 volume = {18},
 year = {1989},
 pages = {1149-1178}
}

@article{JS2, 
 author={M. Jerrum and A. Sinclair}, 
 title = {Polynomial-time Approximation Algorithms for the Ising Model},
 journal = {SIAM J. Comp.}, 
 volume = {22},
 year = {1993},
 pages = {1087-1116}
}

@article{GL1,
 author= {A. Galluccio and M. Loebl}, 
 title= {Even/odd dipaths in planar digraphs}, 
 journal={Optimization Methods and Software},
 volume={3},
 year={1994},
 pages={225-236}
}

@article{GL2,
 author= {A. Galluccio and M. Loebl}, 
 title= {Cycles of prescribed modularity in planar digraphs}, 
 journal= {Jour. of Algorithms},
 volume={21}, 
 year= {1996},
 pages={51-70}
}

@article{GL3,
 author= {A. Galluccio and M. Loebl}, 
 title= {(p,q)-odd digraphs}, 
 journal={Jour. of Graph Theory},
 volume={23},
 year= {1996},
 pages = {175-184}
}

@article{GL4,
 author= {A. Galluccio and M. Loebl}, 
 title= {Even Directed Cycles in {H}-free Digraphs}, 
 journal={Technical Report 410, IASI-CNR}, 
 year= {1995},
 note= {In publication on J. of Algorithms} 
}

@article{GL5,
 author= {A. Galluccio and M. Loebl}, 
 title= {Even Cycles and {H}-homeomorphisms}, 
 journal={Technical Report 424, IASI-CNR}, 
 year= {1995},
 note= {Submitted for publication.} 
}

@article{GL6,
 author= {A. Galluccio and M. Loebl}, 
 title= {A Theory of Pfaffian Orientations {I}: Perfect Matchings 
         and Permanents}, 
 journal={Technical Report 452, IASI-CNR}, 
 year= {1997},
}

@article{GL7,
 author= {A. Galluccio and M. Loebl}, 
 title= {A Theory of Pfaffian Orientations {II}: 
         {T}-joins, $k$-cuts, and {D}uality of enumeration}, 
 journal={Technical Report 97-361, Charles University, Prague}, 
 year= {1997},
}
 

@article{Hall,
 author={D. W. Hall},
 title={A note on primitive skew curves},
 journal={Bull. Amer. Math. Soc.},
 volume={49},
 year={1943},
 pages={935-937}
}

@Techreport{HL,
 author= {W. Hochstaettler and M. Loebl}, 
 title={On bases of circuit lattices}, 
 institution={University of Waterloo},
 number={CORR 96-02},
 month={January},
 year={1996}
}

@article{KLM,
 author={V. Klee and R. Ladner and R. Manber}, 
 title= {Signsolvability revisited}, 
 journal={Linear Algebra Appl.}, 
 volume= {59},
 year= {1984}, 
 pages={131-157}
}

@article{Khu,
 author={S. Khuller},
 title={Extending planar algorithms to ${K}_{3,3}$-free graphs},
 journal={Inform. and Comput.},
 volume={84},
 year={1990},
 pages={13-25}
}

@article{Lanc,
 author= {K. Lancaster}, 
 title= {The scope of qualitative economics}, 
 journal={Rev. Econom. Studies }, 
 volume= {29},
 year= {1962}, 
 pages={99-132}
}


@article{LI2,
 author={C. H. C. Little},
 title = {A characterization of convertible (0,1)-matrices}, 
 journal = {JCT(B)},
 volume = {18},
 year = {1975},
 pages = {187-208},
}

@article{LiP,
 author={C.H.C. Little and J.M. Pla},
 title={Sur l'utilisation d'un pfaffien dans l'etude des couplages 
        parfaits d'un graphe},
 journal={C.R.Acad.Sci.Paris Ser.I Math.},
 volume={274},
 year={1972}
}


@article{LO1,
 author={L. Lov\'asz},
 title ={Matching structure and the matching lattice}, 
 journal = {JCT(B)}, 
 volume = {43},
 year = {1987},
 pages = {187-222}
}



@article{LS,
 author={L. Lov\'asz and A. Seres},
 title ={The cocycle lattice of binary matroids},
 journal = {Europ. J. Comb.},
 volume = {14},
 year = {1993},
 pages = {241-250} 
}

@inproceedings{Moh,
 author= {B. Mohar}, 
 title= {Embedding graphs in an arbitrary surface in linear time}, 
 booktitle = {Proc. of ACM Symposium on Theory of Computing},
 year = {1996},
 publisher = {ACM}
}
 
 journal={Crelle's J.}, 
 volume= {38},
 year= {1847}, 
 pages={93-96}
}



@Techreport{NuPe,
 author={Z. Nutov and M.~Penn},
 title={Minimum feedback arc set and maximum integral dicycle 
        packing algorithms in $K_{3,3}$-free digraphs},
 institution={Technion},
 month={June},
 year={1994}
}

@article{Pla,
 author={J.M. Pla},
 title={Sur l'utilisation d'un pfaffien dans l'etude des couplages 
        parfaits d'un graphe},
 journal={C.R.Acad.Sci.Paris Ser.I Math.},
 volume={260},
 year={1965}
}


@article{PR,
 author= {S. Poljak and F. Rendl},
 title= {Solving the max-cut problem using eigenvalues},
 journal={Discr. Appl. Math.},
 volume={62}, 
 year= {1995},
 pages={249-278}
}


@article{Robb,
author={H.E. Robbins},
title={A theorem on graphs, with an application to a problem of 
       traffic control},
journal={Americ. Mathem. Monthly},
volume={46},
year={1939},
pages={281-283}
}

@article{SCH,
author={A. Schrijver},
title={Finding $k$-disjoint paths in a directed planar graph},
journal={SIAM J. Comput.},
volume={23},
year={1994},
pages={780-788}
}

@article{Sey1, 
 author= {P.~D. Seymour}, 
 title= {On the two coloring of hypergraphs}, 
 journal= {Quart. J. Math. Oxford}, 
 volume= {25},
 year= {1974},
 pages={303-312}
}
 
@article{Sey2, 
 author= {P.~D. Seymour}, 
 title ={Directed circuits on a torus},
 journal={Combinatorica},
 volume={11},
 year={1991},
 pages={261-273}
}

@article{Sey3, 
 author= {P.~D. Seymour}, 
 title ={Decomposition of regular matroids}, 
 journal={J. Comb. Th. B}, 
 volume={28},
 year={1980},
 pages={305-359} 
}


@article{ST,
 author={P.~D. Seymour and C. Thomassen}, 
 title={Characterization of even directed graphs},
 journal={J. Comb. Th. B},
 volume={42},
 year={1987},
 pages={36-45}
}

@article{RST,
 author={W.~McCuaig and N.~Robertson and P.~D.~Seymour and R.~Thomas}, 
 title={Permanents, Pfaffian Orientations, and Even Directed 
        Circuits}, 
 journal={},
 volume={},
 year={1996},
 pages={},
 note={Preprint}
}
 


@article{TH1,
 author= {C. Thomassen}, 
 title= {Even cycles in directed graphs}, 
 journal= {European J. Combin.}, 
 volume= {6},
 year= {1985},
 pages={72-87}
}
 
@article{TH2,
 author= {C. Thomassen}, 
 title= {Sign-nonsingular matrices and even cycles in directed graphs}, 
 journal= {Linear Algebra and Appl.},
 volume= {75},
 year= {1986},
 pages={27-41}
}
 
@article{TH3,
 author= {C. Thomassen}, 
 title= {The even cycle problem for planar digraphs}, 
 journal={J. Algorithms},
 volume= {15},
 year= {1993}, 
 pages={61-75}
}
 
@article{TH4,
 author= {C. Thomassen}, 
 title= {The even cycle problem for directed graphs}, 
 journal={J. Am. Math. Soc.}, 
 volume= {5},
 year= {1992}, 
 pages={217-229}
}

@article{TH5,
 author= {C. Thomassen}, 
 title= {On the presence of disjoint subgraphs of a specified type}, 
 journal={J. Graph Theory}, 
 volume= {12},
 year= {1988}, 
 pages={101-111}
}

@article{Val,
 author= {L. G. Valiant}, 
 title= {The complexity of computing the permanent}, 
 journal= {Theoret. Comput. Sci.}, 
 volume= {8},
 year= {1979},
 pages={189-201}
}

@article{Vaz,
 author={V.~V.~Vazirani},
 title={{NC} algorithms for computing the number of perfect 
         matchings in ${K}_{3,3}$-free graphs and related problems},
 journal={Inform. and Comput.},
 volume={80},
 year={1989},
 pages={152-164}
}

@article{VY,
 author={V. V. Vazirani and M. Yannakakis}, 
 title= {Pfaffian orientations, 0-1 permanents and even cycles in directed 
         graphs}, 
 journal={Discr. Appl. Math.},
 volume= {25},
 year= {1989}, 
 pages={179-190}
}
 

@article{Polya,
 author={G. Polya},
 title = {Aufgabe 424}, 
 journal = {Arch. Math. Phys.},
 volume = {20},
 year = {1913},
 pages = {271}
}


@article{Szego,
 author={G. Szego},
 title = {Lozung zu 424}, 
 journal = {Arch. Math. Phys.},
 volume = {21},
 year = {1913},
 pages = {291-292}
} 


@article{KAST1,
 author={P. W. Kasteleyn},
 title = {Dimer Statistics and Phase Transitions},
 journal = {Jour. Math. Physics},
 volume = {4},
 year = {1963},
 pages = {287-293}
}

@article{KAST2,
 author={P. W. Kasteleyn},
 title = {The Statistics of Dimers on a Lattice}, 
 journal = {Physica},
 volume = {27},
 year = {1961},
 pages = {1209-1225}
}

@article{Wag1, 
 author={K. Wagner}, 
 title = {Beweis einer Abschwachung der {H}adwiger-Vermutung},
 journal = {Math. Ann.}, 
 volume = {153},
 year = {1964},
 pages = {139-141}
}


@book{LP,
 author={L.Lov\'asz and M. Plummer},
 title={Matching Theory},
 publisher= {Academic Press},
 year={1986}
}
 


@article{kw,
author={M. Kac and J.C. Ward},
title={A Combinatorial Solution of the Two-Dimensional {I}sing 
Model},
journal={Physical Review}, 
volume={88},
year={1952}
}

@article{pw,
author={R.B. Potts and  J.C. Ward},
title={The Combinatorial Method and the Two-Dimensional {I}sing Model},
journal={Progress of Theoretical Physics},
volume={ 13},
year={1955}
}

@book{w2,
author={D.J.A. Welsh},
title={Complexity: Knots, Colourings and Counting},
note={London Mathematical Society Lecture Note Series 186},
publisher={   Cambridge University Press},
year= {1993}
}

@article{W4,
author={ D.J.A.Welsh},
title={Counting Colourings And Flows In Random Graphs},
journal={Bolyai Society Mathematical Studies}, 
volume={2}, 
year={1996}
}

@article{Fish,
author={ M.E. Fisher},
title={On the Dimer Solution of Planar {I}sing Models},
journal={Journal of Mathematical Physics 7}, 
volume={10}, 
year={1966}
}

\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{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.