# Irreducibility of the Tutte polynomial of an embedded graph

Joanna A. Ellis-Monaghan
Korteweg-de Vries Instituut voor Wiskunde
Universiteit van Amsterdam, Science Park 105-107, 1098 XG
Amsterdam, The Netherlands
<EMAIL_ADDRESS>Andrew J. Goodall
Computer Science Institute (IÚUK), Charles University
Malostranské nám. 25,
118 00 Praha 1, Czech Republic
<EMAIL_ADDRESS>Iain Moffatt
Department of Mathematics
Royal Holloway, University of London
Egham, UK
<EMAIL_ADDRESS>Steven Noble
Birkbeck, University of London
Malet Street
London, UK
<EMAIL_ADDRESS>Lluís Vena
Universitat Politècnica de Catalunya
Barcelona
Spain
<EMAIL_ADDRESS>
(29th April 2022)

###### Abstract

We prove that the ribbon graph polynomial of a graph embedded in an orientable
surface is irreducible if and only if the embedded graph is neither the
disjoint union nor the join of embedded graphs. This result is analogous to
the fact that the Tutte polynomial of a graph is irreducible if and only if
the graph is connected and non-separable.

Mathematics Subject Classifications: 05C31, 05B35

Keywords: Bollobás–Riordan polynomial, delta-matroid, irreducible, ribbon
graph, ribbon graph polynomial, separable, Tutte polynomial

††Acknowledgements: This work was undertaken while three of the authors
(J.E-M, I.M and S.N.) were visiting the Department of Applied Mathematics
(KAM) and the Computer Science Institute (IÚUK), Charles University, Prague.
They are grateful to KAM and IÚUK for their generous hospitality and excellent
research environment. J.E-M. was hosted and supported by KAM and by the
Fulbright Commission as a Charles–Fulbright Distinguished Chair. A.G. was
supported by Czech Science Foundation GA ČR 19-21082S. I.M. was supported by
KAM and by a Scheme 4 grant from the London Mathematical Society. S.N. was
supported by KAM. L.V. is supported by Beatriu de Pinós BP2018, funded by the
AGAUR (Government of Catalonia) and by the Horizon 2020 programme No 801370,
and was supported by Czech Science Foundation GA ČR 18-13685Y

##  1 Introduction

The _Tutte polynomial_ of a graph $G=(V,E)$ can be defined by

$T(G;x,y):=\sum_{A\subseteq E}(x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)},$ (1)

where $r(A)$ is the rank of the subgraph $(V,A)$ of $G$. It satisfies a
universality property, which roughly means that it contains all graph
parameters that satisfy a linear relation among $G$, $G\backslash e$ and $G/e$
(see e.g. [20, Sec. 2.4] for details). Because of this, the Tutte polynomial
captures a surprisingly diverse range of graph parameters and appears in a
variety of areas, such as statistical physics, knot theory, and coding theory.
(See, for example, [1, 9, 18, 20, 36] for further background.)

A standard property of the Tutte polynomial is that when a graph $G$ is the
disjoint union or the one-point join of graphs $G_{1}$ and $G_{2}$ we have
$T(G;x,y)=T(G_{1};x,y)\,T(G_{2};x,y)$. Thus if $T(G;x,y)$ is irreducible over
$\mathbb{Z}[x,y]$, then $G$ must be connected and non-separable. In the 1970’s
Brylawski [8] conjectured that the converse also holds. This conjecture was
verified in 2001 by Merino, de Mier and Noy [29]. Thus $T(G;x,y)$ is
irreducible over $\mathbb{Z}[x,y]$ (or $\mathbb{C}[x,y]$) if and only if $G$
is a connected and non-separable graph.

An _embedded graph_ (or equivalently a _combinatorial map_ , _ribbon graph_ ,
etc.) can be thought of as a graph drawn on a closed surface in such a way
that its edges do not intersect (except at any common vertices), and such that
its faces are homeomorphic to discs. Our aim is to extend the above
irreducibility result to the setting of embedded graphs.

The analogue of the Tutte polynomial for an embedded graph $\mathbb{G}$ is the
_ribbon graph polynomial_ , $R(\mathbb{G};x,y)$, which is a universal
deletion-contraction invariant for embedded graphs. Its definition differs
from (1) by modifying the rank function so that it records some topological
information about the embedding. For an embedded graph $\mathbb{G}=(V,E)$ and
subset $A$ of $E$, we define $\gamma(A)$ to be the Euler genus of the embedded
subgraph $(V,A)$, which coincides with the genus of a neighbourhood of $(V,A)$
in the surface, in the case that the surface is non-orientable, and twice its
genus in the orientable case. Now let $\sigma(A):=r(A)+\tfrac{1}{2}\gamma(A)$,
and then let

$R(\mathbb{G};x,y):=\sum_{A\subseteq
E}(x-1)^{\sigma(E)-\sigma(A)}(y-1)^{|A|-\sigma(A)}.$ (2)

Although the ribbon graph and Tutte polynomials coincide for graphs embedded
in the sphere, they do not agree in general. We note that the polynomial
$R(\mathbb{G};x,y)$ is, up to a prefactor, a two-variable specialisation of
the well known four-variable Bollobás–Riordan polynomial of [3]. However, as
discussed in Remark 1, there are good reasons to work with $R(\mathbb{G};x,y)$
rather than Bollobás–Riordan polynomial or any of the more general topological
Tutte polynomials in the literature.

We say an embedded graph is a _join_ if it can be obtained from two embedded
graphs via a connected summing operation that acts as follows. Choose a disc
in each surface whose boundary intersects the graph in that surface at exactly
a single non-isolated vertex. Then identify the two discs so that the vertices
on their boundaries are also identified, and then delete the interior of the
identified discs.

A standard property (see [3]) of the ribbon graph polynomial is that if
$\mathbb{G}$ is either the disjoint union or join of $\mathbb{G}_{1}$ and
$\mathbb{G}_{2}$, then
$R(\mathbb{G};x,y)=R(\mathbb{G}_{1};x,y)\,R(\mathbb{G}_{1};x,y)$. We prove
here that the converse holds in the orientable case.

######  Theorem 1.1.

Let $\mathbb{G}$ be a graph embedded in an orientable surface. Then
$R(\mathbb{G};x,y)$ is irreducible over $\mathbb{Z}[x,y]$ (or
$\mathbb{C}[x,y]$) if and only if $\mathbb{G}$ is connected and not a join of
two smaller embedded graphs.

Theorem 1.1 is an analogue of Merino, de Mier and Noy’s result referred to
above that $T(G;x,y)$ is irreducible if and only if $G$ is connected and non-
separable. As with many results for the classical Tutte polynomial, this
irreducibility property is properly understood in terms of matroids, and was
shown in this more general setting. Merino et al. proved that for a matroid
$M$ the polynomial $T(M;x,y)$ is irreducible if and only if $M$ is connected.
(The Tutte polynomial is extended to a matroid by taking $r$ in Equation (1)
to be the rank function of the matroid.) The graph result follows from the
matroid one by considering cycle matroids of graphs.

The situation for the ribbon graph polynomial is similar: many properties of
the ribbon graph polynomial are properly understood in terms of delta-
matroids. Delta-matroids generalise matroids, in essence, by relaxing the
requirement that bases all have the same size, the analogue of bases being
called _feasible sets_. It is well known that many properties of graphs are
actually properties of matroids. Similarly, many properties of embedded graphs
are in fact properties of delta-matroids. In particular, the ribbon graph
polynomial, connectivity and joins can be understood in terms of delta-
matroids (details are provided below), and Theorem 1.1 is properly a result
about delta-matroids:

######  Theorem 1.2.

Let $D$ be an even delta-matroid. Then $T(D;x,y)$ is irreducible over
$\mathbb{Z}[x,y]$ (or $\mathbb{C}[x,y]$) if and only if $D$ is connected.

The orientably embedded graph of Theorem 1.1 is replaced in Theorem 1.2 by an
even delta-matroid, defined as one whose feasible sets all have size of the
same parity; and the ribbon graph polynomial $R(\mathbb{G};x,y)$ is replaced
by $T(D;x,y)$, the Tutte polynomial of the delta-matroid $D$. The latter is a
universal deletion-contraction invariant for delta-matroids (just as the
classical Tutte polynomial is for matroids) and can be defined using a sum
similar to that in Equation (1), replacing the rank function $r$ with the
average of the rank functions of ‘minimum and maximum matroids’ that arise
from a delta-matroid. See Section 3 for details. Similarly to the graphs and
matroids case, Theorem 1.1 follows from Theorem 1.2 by considering the delta-
matroid of an embedded graph.

Here we are considering an analogue of the Tutte polynomial for embedded
graphs. There are many extensions of the Tutte polynomial from graphs to other
types of combinatorial object. Our main motivation in undertaking this work
lies in uncovering what properties are innate to graphs or matroids, and what
properties extend or should extend to a wider class of objects. The
significance of embedded graphs and delta-matroids in this context is that
they provide an effective step in moving away from the classical setting of
graphs and matroids – they are different but not too different. What is
especially interesting about Theorem 1.1 and 1.2 is that very little of the
argument depends upon the specific class of objects (graphs, matroids,
embedded graphs, or delta-matroids) that we are working with. This hints at a
larger, yet to be understood structure that would help explain the
irreducibility of graph polynomials such as the Tutte polynomial.

######  Remark 1.

Our interest here is in extensions of the Tutte polynomial to graphs that are
cellularly embedded in surfaces (the cellular condition means that the faces
are homeomorphic to discs). It is not obvious how the Tutte polynomial should
be extended from graphs to embedded graphs, and many candidates have been
proposed [2, 3, 21, 22, 25, 26, 27, 28, 32, 33, 34]. It is natural to ask why
we chose the ribbon graph polynomial $R(\mathbb{G};x,y)$ as the analogue of
the Tutte polynomial, rather than any of these other graph polynomials.

The Tutte polynomial of a graph satisfies a deletion-contraction recurrence
that allows its expression in terms of its evaluations on trivial graphs.
While all of the polynomials mentioned above have deletion-contraction
relations that apply to particular types of edges of a cellularly embedded
graph, only the ribbon graph polynomial has a “full” deletion-contraction
definition that applies to all edge-types.

In more detail, there is a way to associate a “canonical Tutte polynomial”
with a class of combinatorial objects [17, 26]. The resulting polynomials are
universal deletion-contraction invariants for that class, just as the
classical Tutte polynomial is for the class of graphs. In this framework, the
ribbon graph polynomial $R(\mathbb{G};x,y)$ arises as the polynomial
associated with graphs that are cellularly embedded in surfaces, and hence is
the universal deletion-contraction invariant for this class. (A similar
comment holds for the delta-matroid version of the ribbon graph polynomial.)
All of the other topological graph polynomials mentioned above arise in this
framework as deletion-contraction invariants associated with other types of
embedded graphs (for example, the Bollobás–Riordan polynomial arises as the
universal deletion-contraction invariant for graphs that are non-cellularly
embedded in surfaces). See [25, 26, 32, 33] for details.

##  2 Background and notation

###  2.1 Ribbon graphs

It is convenient to realise embedded graphs as ribbon graphs. We give a brief
overview of ribbon graphs, referring the reader to [19] or [24] (where they
are called reduced band decompositions) for additional details, including
their equivalence with (cellularly) embedded graphs. A ribbon graph is a
structure that arises by taking a regular neighbourhood of a graph embedded in
a surface while keeping the vertex–edge structure of the graph. Informally it
can be thought of as “a graph with vertices as discs and edges as ribbons”.
Formally, a _ribbon graph_ $\mathbb{G}=\left(V,E\right)$ is a surface with
boundary represented as the union of two sets of discs, a set $V$ of vertices,
and a set $E$ of edges such that: (1) the vertices and edges intersect in
disjoint line segments; (2) each such line segment lies on the boundary of
precisely one vertex and precisely one edge; (3) every edge contains exactly
two such line segments.

Graph-theoretic terminology naturally extends to ribbon graphs. A _ribbon
subgraph_ $\mathbb{H}$ of $\mathbb{G}$ is a ribbon graph obtained from
$\mathbb{G}$ by removing some of its vertices and edges. It is _spanning_ if
it has the same vertices as $\mathbb{G}$. The _rank_ $r(\mathbb{G})$ of a
ribbon graph $\mathbb{G}=(V,E)$ is its number of vertices minus its number of
connected components, that is, it is the rank of its underlying graph. For
$A\subseteq E$, $r(A)$ is the rank of the ribbon subgraph $(V,A)$ of
$\mathbb{G}$.

Topologically, a ribbon graph is a surface with boundary. A _quasi-tree_ is a
ribbon graph that has exactly one boundary component. A ribbon subgraph
$\mathbb{H}$ is a _spanning quasi-tree_ of a connected ribbon graph
$\mathbb{G}$ if it is a quasi-tree that contains all the vertices of
$\mathbb{G}$. If $\mathbb{G}$ is not connected, then we say $\mathbb{H}$ is a
spanning quasi-tree if for each connected component of $\mathbb{G}$ the ribbon
subgraph of $\mathbb{H}$ obtained by removing vertices and edges not in this
component is a spanning quasi-tree.

A ribbon graph is _orientable_ if it is orientable when considered as a
surface with boundary. The _genus_ of a ribbon graph is its genus as a surface
with boundary. The _Euler genus_ $\gamma(\mathbb{G})$ of a ribbon graph
$\mathbb{G}=(V,E)$ is its genus if it is non-orientable, and twice its genus
if it is orientable. For $A\subseteq E$, $\gamma(A)$ is the Euler genus of the
ribbon subgraph $(V,A)$ of $\mathbb{G}$. A ribbon graph is _plane_ if it has
Euler genus zero (note that we allow plane ribbon graphs to be disconnected).
The _ribbon graph polynomial_ $R(\mathbb{G};x,y)$ of $\mathbb{G}$ is defined
as in Equation (2), where again $\sigma(A):=r(A)+\tfrac{1}{2}\gamma(A)$.

###  2.2 Delta-matroids

We shall work in the setting of delta-matroids and from this recover our
results for embedded graphs. We assume familiarity with the basic definitions
of matroid theory [35], and give an overview of the delta-matroid theory we
use here. We refer the reader to [12, 31] for additional background on delta-
matroids, which were introduced by Bouchet in [4]. Equivalent concepts albeit
using different terminology were also introduced at around the same time in
[10] and [15].

A _delta-matroid_ $D$ comprises a pair $(E,\mathcal{F})$ where $E$ is a finite
set and $\mathcal{F}$ is a non-empty collection of subsets of $E$ with the
property that for all triples $(F_{1},F_{2},e)$ comprising members $F_{1}$ and
$F_{2}$ of $\mathcal{F}$ and an element $e$ of $F_{1}\bigtriangleup F_{2}$,
there is an element $f$ of $F_{1}\bigtriangleup F_{2}$ (which may be equal to
$e$) such that $F_{1}\bigtriangleup\\{e,f\\}\in\mathcal{F}$. This property is
known as the _symmetric exchange axiom_. The members of $\mathcal{F}$ are
called _feasible sets_ , and $E$ is called its _ground set_. It is not
difficult to see that matroids are precisely delta-matroids in which the
feasible sets are equicardinal.

Given a delta-matroid $D$, let $\mathcal{F}(D)$ denote its collection of
feasible sets, and let $\mathcal{F}_{\max}$ and $\mathcal{F}_{\min}$ denote
the subsets of $\mathcal{F}(D)$ comprising the feasible sets with maximum and
minimum size respectively. It is straightforward to show that both
$(E,\mathcal{F}_{\max})$ and $(E,\mathcal{F}_{\min})$ are matroids, known as
the _maximum_ and _minimum_ matroids and denoted by $D_{\max}$ and $D_{\min}$
respectively.

For a matroid $M$, let $r(M)$ denote its rank and let $r_{M}(A)$ denote the
rank of the set $A$ of elements of $M$. For a delta-matroid $D$ with element
set $E$ and set $\mathcal{F}$ of feasible sets, the _delta-matroid rank
function_ , $\rho_{D}$, introduced by Bouchet in [5] is given by

$\rho_{D}(A)=|E|-\min\\{|A\bigtriangleup F|:F\in\mathcal{F}\\}.$

Note that if a delta-matroid $D$ is also a matroid, then $\rho_{D}$ and
$r_{D}$ do not generally coincide. This explains why we do not define the
Tutte polynomial of a delta-matroid by merely replacing $r$ by $\rho$ in
Equation (1).

A _coloop_ of $D$ is an element of $D$ belonging to every feasible set. A
_loop_ of $D$ is an element of $D$ belonging to no feasible set.

Let $D$ be a delta-matroid and $e$ an element of $D$. Suppose first that $e$
is not a coloop of $D$. Then we define $D\backslash e$, the _deletion_ of $e$,
to be the pair

$(E-e,\\{F\in\mathcal{F}\mid e\notin F\\}).$

Now suppose that $e$ is not a loop of $D$. Then we define $D/e$, the
_contraction_ of $e$, to be the pair

$(E-e,\\{F-e\mid F\in\mathcal{F}\text{ and }e\in F\\}).$

If $e$ is either a coloop or a loop of $D$, then one of $D\backslash e$ and
$D/e$ is defined. In this case, we define whichever of $D\backslash e$ and
$D/e$ is so far undefined by setting $D\backslash e=D/e$. It is easy to check
that both $D\backslash e$ and $D/e$ are delta-matroids. Moreover it is also
easy to check that if we perform a sequence of deletions and contractions then
the resulting delta-matroid does not depend on the order in which these
operations are carried out. Thus we may delete and contract sets of elements
without ambiguity. Any delta-matroid obtained from $D$ by deleting and
contracting possibly empty subsets of the elements of $D$ is said to be a
_minor_ of $D$.

For a subset $A$ of the element set of $D$, let $D|A=D\backslash A^{c}$ denote
the delta-matroid formed by deleting the elements of $A^{c}:=E\setminus A$ and
let $\sigma(A)=(r((D|A)_{\max})+r((D|A)_{\min}))/2$. The _width_ $w(D)$ of $D$
is $r(D_{\max})-r(D_{\min})$. Note that $\sigma(A)=r((D|A)_{\min})+w(D|A)/2$.

Just as the spanning trees in a graph give rise to its cycle matroid, the
spanning quasi-trees in a ribbon graph give rise to its delta-matroid. For a
ribbon graph $\mathbb{G}=(V,E)$, the pair $D(\mathbb{G}):=(E,\mathcal{F})$,
where

$\mathcal{F}:=\\{F\subseteq E:F\text{ is the edge set of a spanning quasi-tree
of }\mathbb{G}\\},$

is the _delta-matroid of $\mathbb{G}$_. These delta-matroids can be regarded
as the topological analogues of the cycle matroids of graphs. A delta-matroid
arising from a ribbon graph in this way is said to be _ribbon-graphic_. The
class of ribbon-graphic delta-matroids was first considered by Bouchet in [6],
albeit using very different language. In Proposition 5.3 of [12], it is shown
that $w(D(\mathbb{G}))=\gamma(\mathbb{G})$, and consequently
$\sigma(D(\mathbb{G}))=\sigma(\mathbb{G})$.

##  3 The Tutte polynomial of a delta-matroid

We begin by extending the definition of the Tutte polynomial of a matroid to
delta-matroids. For a delta-matroid $D$ with element set $E$, define its
_Tutte polynomial_ $T(D;x,y)$ by

$T(D;x,y):=\sum_{A\subseteq
E}(x-1)^{\sigma(E)-\sigma(A)}(y-1)^{|A|-\sigma(A)}.$ (3)

Note that if $D$ is a matroid, then for every subset $A$ of its elements,
$r((D|A)_{\min})=r((D|A)_{\max})$, so $\sigma(A)=r(A)$. Therefore our
definition of the Tutte polynomial of a delta-matroid is consistent with the
existing definition of the Tutte polynomial of a matroid and retains several
key properties.

Following [12], the _Bollobás–Riordan polynomial_ of a delta-matroid $D$ is
given by

$\textit{BR}(D;x,y,z):=\sum_{A\subseteq
E}(x-1)^{r_{D_{\min}}(E)-r_{D_{\min}}(A)}y^{|A|-r_{D_{\min}}(A)}z^{w(D|A)}.$

Since $\sigma(D(\mathbb{G}))=\sigma(\mathbb{G})$ for any ribbon graph
$\mathbb{G}$, the ribbon graph polynomial of $\mathbb{G}$ agrees with the
Tutte polynomial of its delta-matroid:
$R(\mathbb{G};x,y)=T(D(\mathbb{G});x,y)$. Similarly, the Bollobás–Riordan
polynomial of a ribbon graph, introduced in [3], agrees with the
Bollobás–Riordan polynomial of its delta-matroid (see Theorem 6.4 of [12]).

The next two results are from [12]. The first is stated on page 52 and the
second is Theorem 6.6(1).

######  Lemma 3.1.

For every delta-matroid $D$,

$T(D;x,y)=(x-1)^{w(D)/2}\textit{BR}(D;x,y-1,1/\sqrt{(x-1)(y-1)}\>).$

######  Proposition 3.2.

For every delta-matroid $D$ with element set $E$,

$v^{\sigma(D)}u^{-w(D)/2}T(D;u/v+1,uv+1)=\sum_{A\subseteq
E}v^{|A|}u^{|E|-\rho_{D}(A)}.$

Recall that a delta-matroid is _even_ if and only if the cardinalities of its
feasible sets all have the same parity. The property of being even is
preserved under deletion and contraction.

######  Corollary 3.3.

For every delta-matroid $D$, the polynomial $T(D;x,y)$ determines the
following:

  1. 1.

the number of elements of $D$;

  2. 2.

the number of feasible sets in $D$ of given size;

  3. 3.

the ranks of the minimum and maximum matroids of $D$;

  4. 4.

the width of $D$;

  5. 5.

whether or not $D$ is even;

  6. 6.

whether or not $D$ is a matroid; and

  7. 7.

in the case where $D$ is the delta-matroid of a ribbon graph $\mathbb{G}$,
whether or not $\mathbb{G}$ is plane.

###### Proof.

It follows from Proposition 3.2 that the minimum degree of $v$ in
$T(D;u/v+1,uv+1)$ is $-\sigma(D)$ and the maximum degree of $v$ in
$T(D;u/v+1,uv+1)$ is $|E(D)|-\sigma(D)$. Thus both $|E(D)|$ and $\sigma(D)$
are determined by $T(D)$.

As $A$ is feasible in $D$ if and only if $\rho_{D}(A)=|E|$, the terms of
$T(D;u/v+1,uv+1)$ with minimum degree in $u$ correspond to the feasible sets
of $D$. Such a set $F$ yields a term $u^{w(D)/2}v^{|F|-\sigma(D)}$, so one may
deduce the number of feasible sets of $D$ of any given size. In particular,
$T(D)$ determines the ranks of the minimum and maximum matroids of the delta-
matroid $D$ and consequently $w(D)$, and whether or not $D$ is even. As $T(D)$
determines the width of $D$, it also determines whether or not $D$ is a
matroid. If $D$ is the ribbon-graphic delta-matroid of a ribbon graph
$\mathbb{G}$, then, since $w(D(\mathbb{G}))=\gamma(\mathbb{G})$, $D$ is a
matroid if and only if $\mathbb{G}$ is plane. ∎

Given delta-matroids $D_{1}=(E_{1},\mathcal{F}_{1})$ and
$D_{2}=(E_{2},\mathcal{F}_{2})$ with disjoint element sets, let $D_{1}\oplus
D_{2}$ denote the delta-matroid with element set $E_{1}\cup E_{2}$ and set of
feasible sets $\\{F_{1}\cup F_{2}:F_{1}\in\mathcal{F}_{1}\text{ and
}F_{2}\in\mathcal{F}_{2}\\}$. We say that a delta-matroid $D$ is _connected_
if there do not exist delta-matroids $D_{1}$ and $D_{2}$ with non-empty
element sets satisfying $D=D_{1}\oplus D_{2}$.

######  Proposition 3.4.

Let $D$ be a delta-matroid $D$ such that $D=D_{1}\oplus D_{2}$. Then

$T(D;x,y)=T(D_{1};x,y)\,T(D_{2};x,y).$

###### Proof.

Let $A_{1}$ and $A_{2}$ be subsets of the element sets of $D_{1}$ and $D_{2}$,
and let $A=A_{1}\cup A_{2}$. Then $D|A=(D_{1}|A_{1})\oplus(D_{2}|A_{2})$.
Moreover for any delta-matroids $D^{\prime}_{1}$ and $D^{\prime}_{2}$ on
disjoint element sets $(D^{\prime}_{1}\oplus
D^{\prime}_{2})_{\min}=(D^{\prime}_{1})_{\min}\oplus(D^{\prime}_{2})_{\min}$
and $(D^{\prime}_{1}\oplus
D^{\prime}_{2})_{\max}=(D^{\prime}_{1})_{\max}\oplus(D^{\prime}_{2})_{\max}$,
so all the relevant parameters are additive over the components $D_{1}$ and
$D_{2}$ of $D$. Hence the result follows. ∎

Following Bouchet [4], for a delta-matroid $D$ and subset $A$ of its elements,
let $D*A$ denote the _twist_ of $D$ with respect to $A$, that is, the delta-
matroid with the same element set as $D$ such that $F$ is feasible in $D*A$ if
and only if $F\bigtriangleup A$ is feasible in $D$. The _dual_ $D^{*}$ of
$D=(E,\mathcal{F})$ is $D*E$. Observe that $w(D)=w(D^{*})$,
$D^{*}/e=(D\backslash e)^{*}$, and $D^{*}\backslash e=(D/e)^{*}$. Recall that
a _loop_ of $D$ is an element that appears in no feasible set of $D$. An
element $e$ of a delta-matroid $D$ is:

  1. 1.

_ordinary_ if $e$ is not a loop in $D_{\min}$;

  2. 2.

_a non-orientable ribbon loop_ if $e$ is a loop in both $D_{\min}$ and
$(D*e)_{\min}$;

  3. 3.

_an orientable ribbon loop_ if $e$ is a loop in $D_{\min}$ but not in
$(D*e)_{\min}$.

Clearly, every element of $D$ is of exactly one of these three types.
Moreover, it is not difficult to see that in an even delta-matroid every
element is either ordinary or an orientable ribbon loop. Note that every loop
is an orientable ribbon loop, but the converse does not generally hold.

The next result follows from Lemma 3.1 and the deletion-contraction
recurrences for $\textit{BR}(D)$ (Corollary 5.10 of [13]). It is possible to
add extra cases corresponding to non-orientable ribbon loops of $D$ or
$D^{*}$, but we omit these as we will not require them.

######  Proposition 3.5.

For every delta-matroid $D$, the following hold.

  1. 1.

If the ground set of $D$ is empty, then $T(D;x,y)=1$.

  2. 2.

If element $e$ is ordinary in both $D$ and $D^{*}$, then

$T(D;x,y)=T(D\backslash e;x,y)+T(D/e;x,y).$

  3. 3.

If element $e$ is ordinary in $D$ and an orientable ribbon loop in $D^{*}$,
then

$T(D;x,y)=(x-1)T(D\backslash e;x,y)+T(D/e;x,y).$

  4. 4.

If element $e$ is an orientable ribbon loop in $D$ and ordinary in $D^{*}$,
then

$T(D;x,y)=T(D\backslash e;x,y)+(y-1)T(D/e;x,y).$

  5. 5.

If element $e$ is an orientable ribbon loop in both $D$ and $D^{*}$, then

$T(D;x,y)=(x-1)T(D\backslash e;x,y)+(y-1)T(D/e;x,y).$

It is well known that the Tutte polynomials of a matroid $M$ and its dual
satisfy $T(M;x,y)=T(M^{*};y,x)$. This relation extends to delta-matroids, as
shown in Theorem 6.6 of [12].

######  Proposition 3.6.

For every delta-matroid $D$, $T(D;x,y)=T(D^{*};y,x)$.

When $D$ is even, this can be proved using Proposition 3.5 and induction.

Let $D$ be a delta-matroid. Recall that a  _coloop_ of $D$ is an element
appearing in every feasible set of $D$. Clearly an element $e$ of $D$ is a
loop if and only if it is a coloop of $D^{*}$.

######  Corollary 3.7.

For every delta-matroid $D$, the following hold.

  1. 1.

If element $e$ is a coloop of $D$, then $T(D;x,y)=xT(D/e;x,y)=xT(D\backslash
e;x,y)$.

  2. 2.

If element $e$ is a loop of $D$, then $T(D;x,y)=yT(D/e;x,y)=yT(D\backslash
e;x,y)$.

One of the many well known evaluations of the Tutte polynomial of a matroid
$M$ is that $T(M;1,1)$ is equal to the number of bases of $M$. As shown in
[12], this evaluation only extends to $T(D)$ when $D$ is a matroid.

######  Proposition 3.8.

For every delta-matroid $D$,

$T(D;1,1)=\begin{cases}\text{the number of bases of $D$}&\text{if $D$ is a
matroid,}\\\ 0&\text{otherwise.}\end{cases}$

We easily obtain the following corollaries.

######  Corollary 3.9.

Let $D$ be a delta-matroid that is not a matroid, and let $M$ be a matroid.
Then $T(D;x,y)\neq T(M;x,y)$.

######  Corollary 3.10.

Let $\mathbb{G}$ be a non-plane ribbon graph, and let $H$ be a graph. Then
$R(\mathbb{G};x,y)\neq T(H;x,y)$.

######  Corollary 3.11.

Let $\mathbb{G}$ be a ribbon graph and $H$ a graph such that
$R(\mathbb{G};x,y)=T(H;x,y)$. Then $\mathbb{G}$ is plane.

##  4 The Beta Invariant

The beta invariant of a matroid was introduced by Crapo in [14] and
encapsulates a surprisingly large amount of information. It was first extended
to delta-matroids in [30], where the focus was on the transition polynomial
rather than the Tutte polynomial. Here we define the beta invariant of a
delta-matroid as follows.

######  Definition 4.1.

The _beta invariant_ , $\beta(D)$, of a delta-matroid $D$ is the coefficient
of $x$ in $T(D;x,y)$.

For the special case of matroids, this coincides with Crapo’s definition from
[14]. This is not the case for the invariant introduced in [30] and defined in
terms of the transition polynomial, but the invariant described here is easily
computed from the one introduced in [30] and vice versa. Versions of Theorems
4.7 and 4.9 below appear in [30], phrased in terms of the transition
polynomial. For completeness, we include proofs which do not depend on any
results from [30].

To deduce properties of $\beta(D)$, we need the following results. The first
follows immediately from the definition of the Tutte polynomial given in
Equation (3).

######  Lemma 4.2.

For every delta-matroid $D$ with element set $E$,

$T(D;0,0)=\sum_{A\subseteq E}(-1)^{\sigma(E)-|A|}=\begin{cases}0&\text{if
$E\neq\emptyset$,}\\\ 1&\text{if $E=\emptyset$.}\end{cases}$

######  Proposition 4.3.

Let $D$ be an even delta-matroid with at least two elements. Then the
coefficients of $x$ and of $y$ in $T(D;x,y)$ are equal.

###### Proof.

We proceed by induction on the number of elements of $D$. We begin by
considering all the possibilities for $D$ when it has two elements. If $D$ has
two elements and is disconnected, then each element is either a loop or a
coloop, so by Corollary 3.7 both the coefficients of $x$ and $y$ are zero. If
$D$ has two elements and is connected, then it is equal to $D(\mathbb{G})$
where $\mathbb{G}$ is either the plane cycle with two edges or the genus one
orientable ribbon graph with one vertex and two edges. In the former case
$T(D;x,y)=x+y$ and in the latter case $T(D;x,y)=2xy-x-y$. So the result holds
when $D$ has two elements.

The inductive step follows by combining Proposition 3.5 with Lemma 4.2. ∎

The following technical lemma is needed in most of the results of this
section. An orientable ribbon loop that is not a loop is said to be a _non-
trivial orientable ribbon loop_.

######  Lemma 4.4.

For an even delta-matroid $D$ and element $e$ of $D$, the following hold.

  1. 1.

If $e$ is a loop or coloop of $D$, then $w(D\backslash e)=w(D/e)=w(D)$.

  2. 2.

If $e$ is ordinary in both $D$ and $D^{*}$, then $w(D\backslash
e)=w(D/e)=w(D)$.

  3. 3.

If $e$ is a non-trivial orientable ribbon loop in $D$ and ordinary in $D^{*}$,
then $w(D\backslash e)=w(D)$ and $w(D/e)=w(D)-2$.

  4. 4.

If $e$ is ordinary in $D$ and a non-trivial orientable ribbon loop in $D^{*}$,
then $w(D\backslash e)=w(D)-2$ and $w(D/e)=w(D)$.

  5. 5.

If $e$ is an orientable ribbon loop in both $D$ and $D^{*}$, then
$w(D\backslash e)=w(D/e)=w(D)-2$.

###### Proof.

If $e$ is a loop of $D$, then $\mathcal{F}(D)=\mathcal{F}(D\backslash
e)=\mathcal{F}(D/e)$. Therefore $w(D\backslash e)=w(D/e)=w(D)$. By duality,
the same conclusion holds if $e$ is a coloop of $D$. This proves (1).

From now on we assume that $e$ is neither a loop nor a coloop of $D$. It
follows from the symmetric exchange axiom that a coloop of $D_{\min}$ is a
coloop of $D$. Thus $e$ is not a coloop of $D_{\min}$. Hence $r((D\backslash
e)_{\min})=r(D_{\min})$. If $e$ is ordinary in $D$, then
$r((D/e)_{\min})=r(D_{\min})-1$. Now suppose that $e$ is a non-trivial
orientable ribbon loop in $D$. Then as $e$ is not a loop, there is a feasible
set containing $e$. Let $F_{2}$ be such a feasible set of minimum possible
size. Let $F_{1}$ be a basis of $D_{\min}$. Applying the symmetric exchange
axiom to $F_{1}$, $F_{2}$ and $e$, we deduce that there is a feasible set of
$D$ containing $e$ and having size at most $r(D_{\min})+2$. As $D$ is even and
$e$ is an orientable ribbon loop, such a set must have size $r(D_{\min})+2$.
Thus $r((D/e)_{\min})=r(D_{\min})+1$. Using duality, we see that
$r((D/e)_{\max})=r(D_{\max})-1$; if $e$ is ordinary in $D^{*}$ then
$r(D\backslash e)_{\max}=r(D_{\max})$, and if $e$ is a non-trivial orientable
ribbon loop in $D^{*}$ then $r((D\backslash e)_{\max})=r(D_{\max})-2$.

Each of the remaining parts of the result now follows by applying the
definition of width. ∎

######  Proposition 4.5.

Let $D$ be an even delta-matroid with at least two elements. Then $\beta(D)$
is either zero or has the same sign as $(-1)^{w(D)/2}$. Moreover, if $D$ has
at least three elements and $e$ is an element of $D$ that is neither a loop
nor a coloop, then the coefficient of $x$ in both terms appearing on the right
side of the equation in each of parts (2)–(5) of Proposition 3.5 is either
zero or has the same sign as $(-1)^{w(D)/2}$.

###### Proof.

We proceed by induction on the number of elements of $D$. In the proof of
Proposition 4.3, we showed that if $D$ has two elements then either
$\beta(D)=0$, $D$ has width zero and $\beta(D)=1$, or $D$ has width two and
$\beta(D)=-1$. So the result holds in this case.

Now suppose that $D$ has at least three elements and $e$ is an element of $D$.
If $e$ is either a loop or a coloop, then by Corollary 3.7 and Lemma 4.2,
$\beta(D)=0$. From now on, we assume that $e$ is neither a loop nor a coloop.
We first prove the assertion about the coefficient of $x$ in any term
appearing on the right side of the equation in a part of Proposition 3.5.

If $e$ is ordinary in both $D$ and $D^{*}$, then by Lemma 4.4,
$w(D)=w(D\backslash e)=w(D/e)$, so the result follows from the inductive
hypothesis.

If $e$ is an orientable ribbon loop in $D$ and ordinary in $D^{*}$, then

$T(D;x,y)=T(D\backslash e;x,y)+(y-1)T(D/e;x,y).$

By Lemma 4.4, $w(D\backslash e)=w(D)$ and $w(D/e)=w(D)-2$. As $D\backslash e$
and $D/e$ have at least two elements, Lemma 4.2 and the inductive hypothesis
imply that the coefficient of $x$ in $T(D\backslash e;x,y)$ is either zero or
has the same sign as $(-1)^{w(D\backslash e)/2}=(-1)^{w(D)/2}$ and the
coefficient of $x$ in $(y-1)T(D/e;x,y)$ is either zero or has the same sign as
$-(-1)^{w(D/e)/2}=(-1)^{w(D)/2}$, so the result follows from the inductive
hypothesis.

The case where $e$ is ordinary in $D$ and an orientable ribbon loop in $D^{*}$
follows either by a very similar argument to the previous case or by applying
the previous case to $D^{*}$ and using Propositions 4.3 and 3.6.

Finally, if $e$ is an orientable ribbon loop in both $D$ and $D^{*}$, then

$T(D;x,y)=(x-1)T(D\backslash e;x,y)+(y-1)T(D/e;x,y).$

By Lemma 4.4, $w(D\backslash e)=w(D/e)=w(D)-2$. As both $D\backslash e$ and
$D/e$ have at least two elements, Lemma 4.2 and the inductive hypothesis imply
that the coefficient of $x$ in each of $(x-1)T(D\backslash e;x,y)$ and
$(y-1)T(D/e;x,y)$ is either zero or has the same sign as
$-(-1)^{w(D/e)/2}=(-1)^{w(D)/2}$, so the result follows from the inductive
hypothesis.

By using Proposition 3.5, it follows immediately that $\beta(D)$ is either
zero or has the same sign as $(-1)^{w(D)/2}$. Hence the result follows by
induction.∎

Bouchet proved the following theorem in the more general context of tight
multimatroids. In a sense that is made precise in [7], even delta-matroids are
equivalent to a subclass of tight multimatroids.

######  Theorem 4.6.

Let $D$ be a connected even delta-matroid with element $e$. Then at least one
of $D\backslash e$ and $D/e$ is connected.

We now obtain the following property of $\beta$ generalizing a result of Crapo
[14] for matroids.

######  Theorem 4.7.

Let $D$ be an even delta-matroid with at least two elements. Then
$\beta(D)\neq 0$ if and only if $D$ is connected. Moreover if $D$ is
connected, then the sign of $\beta(D)$ is the same as that of $(-1)^{w(D)/2}$.

###### Proof.

If $D=D_{1}\oplus D_{2}$ then $T(D;x,y)=T(D_{1};x,y)\,T(D_{2};x,y)$, so by
Lemma 4.2 if $D$ is disconnected then $\beta(D)=0$.

To prove the converse, we proceed by induction on the number of elements of
$D$. If $D$ has two elements and is connected, then from the proof of
Proposition 4.3 we see that $T(D;x,y)=x+y$ or $T(D;x,y)=2xy-x-y$, so the
result holds when $D$ has two elements.

Now suppose that the result holds for all even delta-matroids with fewer than
$n$ elements. Let $D$ be a connected, even delta-matroid having $n>2$
elements.

As $D$ is connected, it has no loop or coloop. Let $e$ be an element of $D$.
By Theorem 4.6 at least one of $D\backslash e$ and $D/e$ is connected. Then
the induction hypothesis implies that at least one of $\beta(D\backslash e)$
and $\beta(D/e)$ is non-zero. Combining this observation with Propositions 3.5
and 4.5, we deduce that $\beta(D)\neq 0$. Applying Proposition 4.5 again, we
see that the sign of $\beta(D)$ is the same as that of $(-1)^{w(D)/2}$. Hence
the result follows by induction. ∎

######  Corollary 4.8.

For an even delta-matroid $D$, the following hold.

  1. 1.

$T(D;x,y)$ is divisible by $x^{i}$ if and only if $D$ has at least $i$
coloops.

  2. 2.

$T(D;x,y)$ is divisible by $y^{j}$ if and only if $D$ has at least $j$ loops.

###### Proof.

If $D$ has at least $i$ coloops, then Corollary 3.7 implies that $T(D;x,y)$ is
divisible by $x^{i}$. Similarly if $D$ has at least $j$ loops, then $T(D;x,y)$
is divisible by $y^{j}$.

Now suppose that $D$ has $i$ loops, $j$ coloops and $k$ components
$D_{1},\ldots,D_{k}$ that are neither loops nor coloops. Then

$T(D;x,y)=x^{i}\,y^{j}\,T(D_{1};x,y)\cdots T(D_{k};x,y).$

For each $l$, $D_{l}$ has at least two elements, so Proposition 4.3 and
Theorem 4.7 imply that $T(D_{l};x,y)=a_{l}(x+y)+p_{l}(x,y)$, where $a_{l}$ is
a non-zero constant and $p_{l}$ is a polynomial in which every monomial has
degree at least two. Thus none of $T(D_{1}),\ldots,T(D_{k})$ is divisible by
either $x$ or $y$. Hence the result follows. ∎

We say that a delta-matroid is _series-parallel_ if there is a plane
2-connected series-parallel network $\mathbb{G}$ such that $D$ is a twist of
$D(\mathbb{G})$. Series-parallel delta-matroids were introduced in [30], where
twisted duals of $D(\mathbb{G})$ were also considered.

The next result is a reformulation of a result from [30]. We include a proof
for completeness. We recall that $U_{2,4}$ and $M(K_{4})$ denote,
respectively, the matroid with four elements in which a set is independent if
and only if it has size at most two and the cycle matroid of the complete
graph with four vertices. We use $\text{{NP}}_{3}$ to denote the delta-matroid
on three elements in which a set is feasible if and only if it has even size.

######  Theorem 4.9.

Let $D$ be an even delta-matroid with at least two elements. Then the
following are equivalent.

  1. 1.

$D$ is series-parallel.

  2. 2.

$\beta(D)=(-1)^{w(D)/2}$.

###### Proof.

Suppose the first condition holds. Then there is a plane 2-connected series-
parallel network $\mathbb{G}$ such that $D$ is a twist of $D(\mathbb{G})$. We
proceed by induction on the number of edges in $\mathbb{G}$. If $\mathbb{G}$
has only two edges, then $\mathbb{G}$ is a cycle with two edges and the result
is easy to check. Otherwise $\mathbb{G}$ has an edge $e$ such that one of
$\mathbb{G}\backslash e$ and $\mathbb{G}/e$ contains a coloop or a loop, and
the other is a plane 2-connected series-parallel network with at least two
edges. Thus one of $D\backslash e$ or $D/e$ contains a loop or a coloop, and
the other is series-parallel. So one of $\beta(D\backslash e)$ and
$\beta(D/e)$ is zero, and the inductive hypothesis together with Proposition
3.5 and Lemma 4.2 imply that the other is $\pm 1$. Hence $\beta(D)=\pm 1$, and
Theorem 4.7 determines the sign to be as stated in the second condition.

Now suppose that $\beta(D)=(-1)^{w(D)/2}$. Suppose for a contradiction that
$D$ is not series-parallel. Then either $D$ is not the twist of a matroid or
it is the twist of a matroid $M$ that is not series-parallel. In the former
case, by Proposition 1.5 of [16], $D$ contains a twist of $\text{{NP}}_{3}$ as
a minor. In the latter case, by, for example, Corollary 12.2.14 of [35], $M$
contains $U_{2,4}$ or $M(K_{4})$ as a minor, so $D$ contains a twist of either
$U_{2,4}$ or $M(K_{4})$ as a minor. Thus we see that $D$ contains a twist of
either $\text{{NP}}_{3}$, $U_{2,4}$ or $M(K_{4})$ as a minor. Let $H$ denote
such a minor. As $D$ is connected (by Theorem 4.7), we may apply Corollary 3.3
of [11] to find a sequence $D=D_{0},D_{1},\ldots,D_{k-1},D_{k}=H$ of connected
minors of $D$ such that for each $i$, $D_{i}$ is obtained from $D_{i-1}$ by
deleting or contracting a single element $e_{i}$. We calculate $T(D)$ by
deleting or contracting each element $e_{i}$ in increasing order of $i$ and
using Theorem 3.5. As each of $D_{0},D_{1}\ldots,D_{k-1}$ is connected, none
of $e_{1},e_{2},\ldots,e_{k}$ is a loop or coloop. Therefore we may apply
Proposition 4.5 to deduce that the contributions to $\beta$ from the two terms
on the right side of the appropriate deletion-contraction relations never have
opposing signs. Thus $|\beta(D)|\geq|\beta(H)|$. It is easy to check that if
$H$ is a twist of $U_{2,4}$, $\text{{NP}}_{3}$ or $M(K_{4})$, and $e$ is an
element of $H$, then both $H\backslash e$ and $H/e$ are connected. Hence by
Proposition 4.5 and Theorem 4.7, $|\beta(H)|\geq 2$. So $|\beta(D)|\geq 2$,
and the result follows. ∎

##  5 Irreducibility of $T(D)$

In this section we prove our two main results, which characterise when
$R(\mathbb{G})$ and $T(D)$ are irreducible. Our approach adapts the argument
from [29].

For a delta-matroid $D$, we let $b_{i,j}(D)$ denote the coefficient of
$x^{i}y^{j}$ in $T(D;x,y)$. When the context is clear, we just write
$b_{i,j}$. By the duality formula of Proposition 3.6, for every delta-matroid
$D$ we have $b_{i,j}(D^{*})=b_{j,i}(D)$.

Brylawski [8] established a collection of affine relations satisfied by the
coefficients of the Tutte polynomial of a matroid. Much later, in a surprising
result, Gordon [23] demonstrated that these affine relations hold much more
generally.

For a delta-matroid with element set $E$, we have $\sigma(\emptyset)=0$, and
for any subset $A$ of $E$ we have $\sigma(A)\leq\max\\{|A|,\sigma(E)\\}$.
These conditions are sufficient to apply Theorem 11 of [23] to show that all
of Brylawski’s affine relations hold for $T(D)$, giving the following.

######  Theorem 5.1.

Let $D$ be an even delta-matroid with element set $E$ and let $n=|E|$. Then,
for all $k$ with $0\leq k<n$,

$\sum_{i=0}^{k}\sum_{j=0}^{k-i}(-1)^{j}\binom{k-i}{j}b_{i,j}=0,$

and

$\sum_{i=0}^{n}\sum_{j=0}^{n-i}(-1)^{j}\binom{n-i}{j}b_{i,j}=(-1)^{n-\sigma(E)}.$

######  Lemma 5.2.

Let $D$ be an even delta-matroid with element set $E$. If $i>\sigma(E)$ or
$j>|E|-\sigma(E)$, then $b_{i,j}=0$. Moreover,

$\sum_{j=0}^{|E|-\sigma(E)}b_{\sigma(E),j}=\sum_{i=0}^{\sigma(E)}b_{i,|E|-\sigma(E)}=1.$

###### Proof.

The first part follows from the definition of $T$ and the observation
preceding Theorem 5.1. Notice that $\sum_{j=0}^{|E|-\sigma(E)}b_{\sigma(E),j}$
is equal to the coefficient of $x^{\sigma(E)}$ in $T(D;x,1)$. Thus, as
$\sigma(\emptyset)=0$,

$\sum_{j=0}^{|E|-\sigma(E)}b_{\sigma(E),j}=\sum_{A\subseteq
E:\sigma(A)=0}(1-1)^{|A|}=1.$

The equation $\sum_{i=0}^{\sigma(E)}b_{i,|E|-\sigma(E)}=1$ can be established
by a similar argument or by using duality. ∎

We now prove our main result on the irreducibility of even delta matroids (see
Theorem 1.2).

###### Proof of Theorem 1.2.

If $D$ is disconnected then there are non-empty delta-matroids $D_{1}$ and
$D_{2}$ such that $D=D_{1}\oplus D_{2}$. Proposition 3.4 implies that $T(D)$
is not irreducible.

Now suppose that $D$ is connected. If $D$ has at most one element then
$T(D;x,y)$ is clearly irreducible, so we may assume that $D$ has at least two
elements.

Suppose there is a non-trivial factorization

$T(D;x,y)=A(x,y)\,C(x,y),$

where $A(x,y)=\sum_{i,j}a_{i,j}x^{i}y^{j}$ and
$C(x,y)=\sum_{i,j}c_{i,j}x^{i}y^{j}$. As $D$ has at least one element, we have
$a_{0,0}c_{0,0}=b_{0,0}=0$. Without loss of generality, we assume that
$a_{0,0}=0$. As $D$ is connected with at least two elements, Theorem 4.7
implies that $b_{1,0}\neq 0$. We have
$b_{1,0}=a_{1,0}c_{0,0}+a_{0,0}c_{1,0}=a_{1,0}c_{0,0}$, so $c_{0,0}\neq 0$ and
$a_{1,0}\neq 0$. Similarly $a_{0,1}\neq 0$ since $b_{0,1}\neq 0$. We shall
obtain a contradiction by proving that $c_{0,0}=0$.

For a polynomial $P(x,y)=\sum_{i,j}p_{i,j}x^{i}y^{j}$, define

$\displaystyle\deg_{x}(P)$ $\displaystyle=\max\\{i:\text{there exists $j$ such
that $p_{i,j}\neq 0$}\\}$ and $\displaystyle\deg_{y}(P)$
$\displaystyle=\max\\{j:\text{there exists $i$ such that $p_{i,j}\neq 0$}\\}.$

Now let $m(P)=\deg_{x}(P)+\deg_{y}(P)$. Then we have $m(T(D))=m(A)+m(C)$.
Furthermore, $\deg_{x}(A)<m(T(D))$ and $\deg_{y}(A)<m(T(D))$.

It follows from Lemma 5.2 that

$1=\sum_{j}b_{\deg_{x}(T(D)),j}=\sum_{k}a_{\deg_{x}(A),k}\sum_{l}c_{\deg_{x}(C),l}$

and similarly, or by duality,

$1=\sum_{i}b_{i,\deg_{y}(T(D))}=\sum_{k}a_{k,\deg_{y}(A)}\sum_{l}c_{l,\deg_{y}(C)}.$

Thus,

$\sum_{k}a_{\deg_{x}(A),k}\neq
0\quad\text{and}\quad\sum_{k}a_{k,\deg_{y}(A)}\neq 0.$ (4)

Now, for $k=0,1,\ldots,m(A)$, let

$A_{k}=\sum_{s=0}^{k}\sum_{t=0}^{k-s}(-1)^{t}\binom{k-s}{t}a_{s,t},$

and, for $\deg_{x}(A)\leq k\leq m(A)$ and $i\geq 0$, let

$A_{k,i}=\sum_{s=0}^{k}\sum_{t=0}^{k-s}(-1)^{t+i}\binom{k-s}{t}a_{s,t+i}.$

Notice that $A_{k,0}=A_{k}$. We now prove a recurrence relation involving
these quantities. If $k>\deg_{x}(A)$ and $i>0$, then, using the identity
$\binom{k-s}{t}=\binom{k-s-1}{t}+\binom{k-s-1}{t-1}$, we have

$\displaystyle A_{k,i-1}$
$\displaystyle=\sum_{s=0}^{k}\sum_{t=0}^{k-s}(-1)^{t+i-1}\binom{k-s}{t}a_{s,t+i-1}$
$\displaystyle=(-1)^{i-1}a_{k,i-1}+\sum_{s=0}^{k-1}\sum_{t=0}^{k-1-s}(-1)^{t+i-1}\binom{k-1-s}{t}a_{s,t+i-1}$
$\displaystyle\phantom{=}{}+\sum_{s=0}^{k-1}\sum_{t=1}^{k-s}(-1)^{t+i-1}\binom{k-1-s}{t-1}a_{s,t+i-1}.$

As $k>\deg_{x}(A)$, we have $a_{k,i-1}=0$. The second and third terms in the
equation above are equal to $A_{k-1,i-i}$ and $A_{k-1,i}$ respectively. Thus,

$A_{k-1,i}=A_{k,i-1}-A_{k-1,i-1}$ (5)

whenever $k>\deg_{x}(A)$ and $i>0$. By Lemma 5.2 and Equation (4),

$A_{\deg_{x}(A),\deg_{y}(A)}=\sum_{s=0}^{\deg_{x}(A)}(-1)^{\deg_{y}(A)}a_{s,\deg_{y}(A)}\neq
0.$

By applying Equation (5) repeatedly we can write $A_{\deg_{x}(A),\deg_{y}(A)}$
as a linear combination of $A_{\deg_{x}(A),0}$, …, $A_{m(A),0}$. As
$A_{k,0}=A_{k}$ we see that there exists $k$ with $\deg_{x}(A)\leq k\leq m(A)$
such that $A_{k}\neq 0$.

The proof is completed by following exactly the proof of Lemma 4 from [29] to
deduce that $c_{0,0}=0$ and thereby reach the desired contradiction. ∎

We conclude by applying Theorem 1.2 to ribbon graphs. A ribbon graph
$\mathbb{G}$ is said to be a _join_ of ribbon graphs $\mathbb{G}_{1}$ and
$\mathbb{G}_{2}$ if $\mathbb{G}$ can be constructed by picking arcs on the
boundaries of a non-isolated vertex in each of $\mathbb{G}_{1}$ and
$\mathbb{G}_{2}$ (the arcs should not intersect any edges), then “gluing
together $\mathbb{G}_{1}$ and $\mathbb{G}_{2}$” by identifying the arcs and
merging the two vertices they lie on into a single vertex of $\mathbb{G}$.
This definition is consistent with that of the join of embedded graphs given
in the introduction.

######  Theorem 5.3.

If $\mathbb{G}$ is an orientable ribbon graph, then $R(\mathbb{G};x,y)$ is
irreducible over $\mathbb{Z}[x,y]$ (or $\mathbb{C}[x,y]$) if and only if
$\mathbb{G}$ is not a disjoint union or join of ribbon graphs.

###### Proof.

By Proposition 5.22 of [12], the delta-matroid $D(\mathbb{G})$ of a ribbon
graph $\mathbb{G}$ is connected if and only if $\mathbb{G}$ is not a disjoint
union or join of ribbon graphs. By Proposition 5.3 of [12], $\mathbb{G}$ is
orientable if and only if $D(\mathbb{G})$ is even. The result then follows
from Theorem 1.2 upon noting that $R(\mathbb{G};x,y)=T(D(\mathbb{G});x,y)$. ∎

Theorem 1.1 is obtained from Theorem 5.3 by rewording it in terms of embedded
graphs.

## References

  * [1] Béla Bollobás, _Modern graph theory_ , Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998.
  * [2] Béla Bollobás and Oliver Riordan, _A polynomial invariant of graphs on orientable surfaces_ , Proc. London Math. Soc. 83 (2001), no. 3, 513–531.
  * [3] , _A polynomial of graphs on surfaces_ , Math. Ann. 323 (2002), no. 1, 81–96.
  * [4] André Bouchet, _Greedy algorithm and symmetric matroids_ , Math. Programming 38 (1987), no. 2, 147–159.
  * [5] , _Representability of $\triangle$-matroids_, Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, vol. 52, North-Holland, Amsterdam, 1988, pp. 167–182.
  * [6] , _Maps and $\triangle$-matroids_, Discrete Math. 78 (1989), no. 1-2, 59–71.
  * [7] , _Multimatroids. III. Tightness and fundamental graphs_ , European J. Combin. 22 (2001), no. 5, 657–677, Combinatorial geometries (Luminy, 1999).
  * [8] Thomas H. Brylawski, _A decomposition for combinatorial geometries_ , Trans. Amer. Math. Soc. 171 (1972), 235–282.
  * [9] Thomas H. Brylawski and James G. Oxley, _The Tutte polynomial and its applications_ , Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 123–225.
  * [10] Ramaswamy Chandrasekaran and Santosh N. Kabadi, _Pseudomatroids_ , Discrete Math. 71 (1988), no. 3, 205–217.
  * [11] Carolyn Chun, Deborah Chun, and Steven D. Noble, _Inductive tools for connected delta-matroids and multimatroids_ , European J. Combin. 63 (2017), 59–69.
  * [12] Carolyn Chun, Iain Moffatt, Steven D. Noble, and Ralf Rueckriemen, _Matroids, delta-matroids and embedded graphs_ , J. Combin. Theory Ser. A 167 (2019), 7–59.
  * [13] , _On the interplay between embedded graphs and delta-matroids_ , Proc. London Math. Soc. 118 (2019), no. 3, 675–700.
  * [14] Henry H. Crapo, _The Tutte polynomial_ , Aequationes Math. 3 (1969), 211–229.
  * [15] Andreas Dress and Timothy F. Havel, _Some combinatorial properties of discriminants in metric vector spaces_ , Adv. in Math. 62 (1986), no. 3, 285–312.
  * [16] Alain Duchamp, _Delta matroids whose fundamental graphs are bipartite_ , Linear Algebra Appl. 160 (1992), 99–112. MR 1137846
  * [17] Clément Dupont, Alex Fink, and Luca Moci, _Universal Tutte characters via combinatorial coalgebras_ , Algebr. Comb. 1 (2018), no. 5, 603–651.
  * [18] Joanna A. Ellis-Monaghan and Criel Merino, _Graph polynomials and their applications I: The Tutte polynomial_ , Structural analysis of complex networks, Birkhäuser/Springer, New York, 2011, pp. 219–255.
  * [19] Joanna A. Ellis-Monaghan and Iain Moffatt, _Graphs on surfaces: Dualities, polynomials, and knots_ , SpringerBriefs in Mathematics, Springer, New York, 2013\.
  * [20] Joanna A. Ellis-Monaghan and Iain Moffatt (eds.), _Handbook of the Tutte polynomial and related topics_ , CRC Press, 2022.
  * [21] Andrew Goodall, Bart Litjens, Guus Regts, and Lluís Vena, _A Tutte polynomial for maps II: the non-orientable case_ , European J. Combin. 86 (2020), 103095, 32.
  * [22] Andrew J. Goodall, Thomas Krajewski, Guus Regts, and Lluís Vena, _A Tutte polynomial for maps_ , Combin. Probab. Comput. 27 (2018), no. 6, 913–945.
  * [23] Gary Gordon, _Linear relations for a generalized Tutte polynomial_ , Electron. J. Combin. 22 (2015), no. 1, P1.79.
  * [24] Jonathan L. Gross and Thomas W. Tucker, _Topological graph theory_ , Wiley, 1987\.
  * [25] Stephen Huggett and Iain Moffatt, _Types of embedded graphs and their Tutte polynomials_ , Math. Proc. Cambridge Philos. Soc. 169 (2020), no. 2, 255–297.
  * [26] Thomas Krajewski, Iain Moffatt, and Adrian Tanasa, _Hopf algebras and Tutte polynomials_ , Adv. in Appl. Math. 95 (2018), 271–330.
  * [27] Vyacheslav Krushkal, _Graphs, links, and duality on surfaces_ , Combin. Probab. Comput. 20 (2011), 267–287.
  * [28] Michel Las Vergnas, _Eulerian circuits of 4-valent graphs imbedded in surfaces_ , Algebraic Methods in Graph Theory (L. Lovász and V. Sós, eds.), North Holland, 1981, pp. 451–478.
  * [29] Criel Merino, Anna de Mier, and Marc Noy, _Irreducibility of the Tutte polynomial of a connected matroid_ , J. Combin. Theory Ser. B 83 (2001), no. 2, 298–304.
  * [30] Criel Merino, Iain Moffatt, and Steven D. Noble, _Series–parallel delta-matroids_ , in preparation.
  * [31] Iain Moffatt, _Delta-matroids for graph theorists_ , Surveys in combinatorics 2019, London Math. Soc. Lecture Note Ser., vol. 456, Cambridge Univ. Press, Cambridge, 2019, pp. 167–220.
  * [32] Iain Moffatt and Ben Smith, _Matroidal frameworks for topological Tutte polynomials_ , J. Combin. Theory Ser. B 133 (2018), 1–31.
  * [33] Iain Moffatt and Maya Thompson, _Deletion-contraction and the surface Tutte polynomial_ , in preparation.
  * [34] Seiya Negami, _Polynomial invariants of embeddings of graphs on closed surfaces_ , Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem. (1995), no. 42, 1–10.
  * [35] James G. Oxley, _Matroid theory_ , second ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford Univ. Press, Oxford, 2011.
  * [36] Dominic J. A. Welsh, _Complexity: knots, colourings and counting_ , London Mathematical Society Lecture Note Series, vol. 186, Cambridge University Press, Cambridge, 1993.