% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{needspace}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
\usepackage{ytableau}
\usepackage{tabu}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, June 26, 2016 18:08:28}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{TODO}
\newenvironment{todo}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{obsolete}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{obsolete}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\Sym}{\operatorname{Sym}}
\newcommand{\Mat}{\operatorname{M}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newcommand\arcstr{\ar@/^1pc/}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{The filtered Tutte polynomial}
\ohead{\today}
\begin{document}

\title{The filtered Tutte polynomial}
\author{Darij Grinberg (, Alexander Postnikov?, Nan Li?)}
\date{\today}
\maketitle
\tableofcontents

In this note, we shall prove a generalization of a conjecture made in
\cite[Question 21.7]{LiPost}.

\section{Introduction}

\begin{todo}
Write an introduction.
\end{todo}

\section{Matroids}

\begin{definition}
In the following, $\mathbb{N}$ shall always denote the set $\left\{
0,1,2,\ldots\right\}  $. For any set $E$, we let $\mathcal{P}\left(  E\right)
$ denote the powerset of $E$.
\end{definition}

We recall the basic properties of matroids. We will actually use rather little
from the theory of matroids; \cite[\S 10.1--\S 10.2]{Schrij13} is a perfectly
sufficient reference for our purposes.

Let us first give a definition of a matroid.

\begin{definition}
\label{def.matroid}A \textit{matroid} means a pair $\left(  E,\mathcal{I}%
\right)  $ of a finite set $E$ and a set $\mathcal{I}\subseteq\mathcal{P}%
\left(  E\right)  $ satisfying the following axioms:

\begin{itemize}
\item We have $\varnothing\in\mathcal{I}$.

\item If $Y\in\mathcal{I}$ and $Z\in\mathcal{P}\left(  E\right)  $ are such
that $Z\subseteq Y$, then $Z\in\mathcal{I}$.

\item If $Y\in\mathcal{I}$ and $Z\in\mathcal{I}$ are such that $\left\vert
Y\right\vert <\left\vert Z\right\vert $, then there exists some $x\in
Z\setminus Y$ such that $Y\cup\left\{  x\right\}  \in\mathcal{I}$.
\end{itemize}

When $\left(  E,\mathcal{I}\right)  $ is a matroid, a subset $S$ of $E$ is
said to be \textit{independent} (for this matroid) if and only if
$S\in\mathcal{I}$.

When $\left(  E,\mathcal{I}\right)  $ is a matroid, the set $E$ is called the
\textit{ground set} of the matroid $\left(  E,\mathcal{I}\right)  $.
\end{definition}

Definition \ref{def.matroid} is how a matroid is defined in \cite[\S 10.1]%
{Schrij13} and in \cite[Definition 3.15]{Martin15} (where it is called a
\textquotedblleft(matroid) independence system\textquotedblright). There exist
other definitions of a matroid, which turn out to be equivalent.

\begin{definition}
\label{def.basis}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Let
$S\in\mathcal{P}\left(  E\right)  $. A \textit{basis} of $S$ (for the matroid
$M$) means a maximum-size independent (for $M$) subset of $S$.
\end{definition}

\begin{definition}
\label{def.rank}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Then, a
function $r_{M}:\mathcal{P}\left(  E\right)  \rightarrow\mathbb{N}$ is defined
by%
\begin{equation}
r_{M}\left(  S\right)  =\max\left\{  \left\vert Z\right\vert \ \mid
\ Z\in\mathcal{I}\text{ and }Z\subseteq S\right\}
\ \ \ \ \ \ \ \ \ \ \text{for every }S\subseteq E. \label{eq.def.rank.def}%
\end{equation}
The axioms of a matroid show that if $S\subseteq E$, and if $Z$ is a basis of
$S$ (for $M$), then $r_{M}\left(  S\right)  =\left\vert Z\right\vert $.

The function $r_{M}$ is called the \textit{rank function} of $M$. For every
$S\in\mathcal{P}\left(  E\right)  $, the number $r_{M}\left(  S\right)  $ is
called the \textit{rank} of $S$ (for $M$). Clearly,%
\begin{equation}
r_{M}\left(  S\right)  \leq\left\vert S\right\vert
\ \ \ \ \ \ \ \ \ \ \text{for every }S\subseteq E. \label{eq.def.rank.upperbd}%
\end{equation}
Moreover, $r_{M}\left(  \varnothing\right)  =0$ and%
\begin{equation}
r_{M}\left(  S\right)  \leq r_{M}\left(  T\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }S\subseteq T\subseteq E.
\label{eq.def.rank.incr}%
\end{equation}

\end{definition}

The following facts about bases for matroids are fundamental (and easy to
prove), and will be used without explicit mention:

\begin{proposition}
\label{prop.basis.basics}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
Let $S\in\mathcal{P}\left(  E\right)  $.

\textbf{(a)} There exists at least one basis of $S$ (for $M$).

\textbf{(b)} If $U$ is any independent (for $M$) subset of $S$, then there
exists a basis $T$ of $S$ such that $U\subseteq T$. (In other words, every
independent subset of $S$ can be extended to a basis of $S$.)

\textbf{(c)} The bases of $S$ are precisely the inclusion-maximal independent
subsets of $S$.

\textbf{(d)} Every basis of $S$ has the same size.

\textbf{(e)} If $U$ is any independent subset of $S$, then $\left\vert
U\right\vert \leq r_{M}\left(  S\right)  $.
\end{proposition}

\begin{corollary}
\label{cor.I-from-rank}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
Then,%
\[
\mathcal{I}=\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid\ r_{M}\left(
S\right)  =\left\vert S\right\vert \right\}  .
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.I-from-rank}.]Let $U\in\mathcal{I}$. Thus, $U$ is
an independent set for $M$ (since the independent sets for $M$ are the
elements of $\mathcal{I}$). Consequently, $U$ is an independent subset of $U$.
Thus, $U$ is a maximum-size independent subset of $U$ (since $U$ is a
maximum-size subset of $U$). In other words, $U$ is a basis of $U$ (by the
definition of a \textquotedblleft basis\textquotedblright). Hence,
$r_{M}\left(  U\right)  =\left\vert U\right\vert $. Thus, we have $U\in
I\subseteq\mathcal{P}\left(  E\right)  $ and $r_{M}\left(  U\right)
=\left\vert U\right\vert $. In other words, $U\in\left\{  S\in\mathcal{P}%
\left(  E\right)  \ \mid\ r_{M}\left(  S\right)  =\left\vert S\right\vert
\right\}  $.

Let us now forget that we fixed $U$. We thus have shown that \newline%
$U\in\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid\ r_{M}\left(  S\right)
=\left\vert S\right\vert \right\}  $ for every $U\in\mathcal{I}$. In other
words,%
\begin{equation}
\mathcal{I}\subseteq\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid
\ r_{M}\left(  S\right)  =\left\vert S\right\vert \right\}  .
\label{pf.cor.I-from-rank.1}%
\end{equation}


On the other hand, let $V\in\left\{  S\in\mathcal{P}\left(  E\right)
\ \mid\ r_{M}\left(  S\right)  =\left\vert S\right\vert \right\}  $. Thus,
$V\in\mathcal{P}\left(  E\right)  $ and $r_{M}\left(  V\right)  =\left\vert
V\right\vert $.

We know that there exists at least one basis of $V$ (by Proposition
\ref{prop.basis.basics} \textbf{(b)}, applied to $S=V$). Fix such a basis, and
denote it by $Q$. Then, $r_{M}\left(  V\right)  =\left\vert Q\right\vert $
(since $Q$ is a basis of $V$). Hence, $\left\vert Q\right\vert =r_{M}\left(
V\right)  =\left\vert V\right\vert $. Combined with $Q\subseteq V$, this shows
that $Q=V$. But $Q$ is a basis of $V$, and thus an independent set. In other
words, $Q\in\mathcal{I}$. Hence, $V=Q\in\mathcal{I}$.

Let us now forget that we fixed $V$. We thus have shown that $V\in\mathcal{I}$
for every $V\in\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid\ r_{M}\left(
S\right)  =\left\vert S\right\vert \right\}  $. In other words,%
\[
\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid\ r_{M}\left(  S\right)
=\left\vert S\right\vert \right\}  \subseteq\mathcal{I}.
\]
Combining this with (\ref{pf.cor.I-from-rank.1}), we obtain $\mathcal{I}%
=\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid\ r_{M}\left(  S\right)
=\left\vert S\right\vert \right\}  $. This proves Corollary
\ref{cor.I-from-rank}.
\end{proof}

\begin{corollary}
\label{cor.M-from-rank}Let $M$ and $M^{\prime}$ be two matroids with one and
the same ground set $E$. Assume that $r_{M}=r_{M^{\prime}}$. Then,
$M=M^{\prime}$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.M-from-rank}.]Write the matroids $M$ and
$M^{\prime}$ as $\left(  E,\mathcal{I}\right)  $ and $\left(  E,\mathcal{I}%
^{\prime}\right)  $, respectively. Then, Corollary \ref{cor.I-from-rank} shows
that%
\begin{equation}
\mathcal{I}=\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid
\ \underbrace{r_{M}}_{=r_{M^{\prime}}}\left(  S\right)  =\left\vert
S\right\vert \right\}  =\left\{  S\in\mathcal{P}\left(  E\right)
\ \mid\ r_{M^{\prime}}\left(  S\right)  =\left\vert S\right\vert \right\}  .
\label{pf.cor.M-from-rank.1}%
\end{equation}


But Corollary \ref{cor.I-from-rank} (applied to $M^{\prime}$ and
$\mathcal{I}^{\prime}$ instead of $M$ and $\mathcal{I}$) shows that%
\[
\mathcal{I}^{\prime}=\left\{  S\in\mathcal{P}\left(  E\right)  \ \mid
\ r_{M^{\prime}}\left(  S\right)  =\left\vert S\right\vert \right\}  .
\]
Comparing this with (\ref{pf.cor.M-from-rank.1}), we obtain $\mathcal{I}%
=\mathcal{I}^{\prime}$. Hence, $M=\left(  E,\underbrace{\mathcal{I}%
}_{=\mathcal{I}^{\prime}}\right)  =\left(  E,\mathcal{I}^{\prime}\right)
=M^{\prime}$. This proves Corollary \ref{cor.M-from-rank}.
\end{proof}

\begin{definition}
\label{def.nullity}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Then,
a function $n_{M}:\mathcal{P}\left(  E\right)  \rightarrow\mathbb{N}$ is
defined by%
\begin{equation}
n_{M}\left(  S\right)  =\left\vert S\right\vert -r_{M}\left(  S\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }S\subseteq E. \label{eq.def.nullity.def}%
\end{equation}
(This is well-defined due to (\ref{eq.def.rank.upperbd}).)

The function $n_{M}$ is called the \textit{nullity function} of $M$. For every
$S\in\mathcal{P}\left(  E\right)  $, the number $n_{M}\left(  S\right)  $ is
called the \textit{nullity} of $S$ (for $M$).
\end{definition}

\begin{proposition}
\label{prop.nullity.monotone}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.

\textbf{(a)} We have $n_{M}\left(  \varnothing\right)  =0$.

\textbf{(b)} We have
\begin{equation}
n_{M}\left(  S\right)  \leq n_{M}\left(  T\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }S\subseteq T\subseteq E.
\label{eq.prop.nullity.monotone.b.eq}%
\end{equation}

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.nullity.monotone}.]\textbf{(a)} This follows
from the definition of $n_{M}$ and from $r_{M}\left(  \varnothing\right)  =0$.

\textbf{(b)} Let $S\subseteq T\subseteq E$. Pick a basis $Z$ of $S$ (this is
possible, since a basis of $S$ exists). Then, $r_{M}\left(  S\right)
=\left\vert Z\right\vert $. But $Z$ is a basis of $S$, and thus an independent
set. Hence, we can extend $Z$ to a basis of $T$ (according to Proposition
\ref{prop.basis.basics} \textbf{(b)}). In other words, there exists a basis
$Y$ of $T$ such that $Z\subseteq Y$. Pick such a $Y$. Since $Y$ is a basis of
$T$, we have $r_{M}\left(  T\right)  =\left\vert Y\right\vert $.

The set $Y$ is a basis of $T$, thus a maximum-size independent subset of $T$.

But $Y\setminus Z\subseteq T\setminus S$\ \ \ \ \footnote{\textit{Proof.} Let
$y\in Y\setminus Z$. Hence, $y\notin Z$.
\par
Assume (for the sake of contradiction) that $y\in S$. The set $Z\cup y$ is a
subset of $Y$ (since $Z\subseteq Y$ and $y\in Y\setminus Z\subseteq Y$) and
thus is independent (since $Y$ is independent). Moreover, $\left\vert Z\cup
y\right\vert =\left\vert Z\right\vert +1$ (since $y\notin Z$). Furthermore,
$Z\cup y\subseteq S$ (since $Z\subseteq S$ and $y\in S$). Hence, $Z\cup y$ is
an independent subset of $S$. Therefore, $\left\vert Z\cup y\right\vert
\leq\left\vert Z\right\vert $ (since $Z$ is a maximum-size independent subset
of $S$). This contradicts $\left\vert Z\cup y\right\vert =\left\vert
Z\right\vert +1$. This contradiction shows that our assumption (that $y\in S$)
was wrong. Hence, we have $y\notin S$. Combined with $y\in Y\setminus
Z\subseteq Y\subseteq T$, this yields $y\in T\setminus S$.
\par
Now, we have proven this for every $y\in Y\setminus Z$. In other words,
$Y\setminus Z\subseteq T\setminus S$, qed.}. Hence, $\left\vert Y\setminus
Z\right\vert \leq\left\vert T\setminus S\right\vert =\left\vert T\right\vert
-\left\vert S\right\vert $ (since $S\subseteq T$). Now,%
\begin{align*}
\underbrace{r_{M}\left(  T\right)  }_{=\left\vert Y\right\vert }%
-\underbrace{r_{M}\left(  S\right)  }_{=\left\vert Z\right\vert }  &
=\left\vert Y\right\vert -\left\vert Z\right\vert =\left\vert Y\setminus
Z\right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{since }Z\subseteq Y\right) \\
&  \leq\left\vert T\right\vert -\left\vert S\right\vert .
\end{align*}
In other words, $\left\vert S\right\vert -r_{M}\left(  S\right)
\leq\left\vert T\right\vert -r_{M}\left(  T\right)  $. Since $n_{M}\left(
S\right)  =\left\vert S\right\vert -r_{M}\left(  S\right)  $ and $n_{M}\left(
T\right)  =\left\vert T\right\vert -r_{M}\left(  T\right)  $ (by the
definition of $n_{M}$), this rewrites as $n_{M}\left(  S\right)  \leq
n_{M}\left(  T\right)  $. This proves Proposition \ref{prop.nullity.monotone}
\textbf{(b)}.
\end{proof}

Next, we shall define loops and coloops in a matroid (following, for example,
\cite[Definition 3.35]{Martin15}):

\begin{definition}
Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Let $e\in E$. We write
$r_{M}\left(  e\right)  $ for $r_{M}\left(  \left\{  e\right\}  \right)  $.
Also, if $S$ is any subset of $E$, then we abbreviate the sets $S\setminus
\left\{  e\right\}  $ and $S\cup\left\{  e\right\}  $ by $S\setminus e$ and
$S\cup e$, respectively.

\textbf{(a)} The element $e$ is said to be a \textit{loop} (of $M$) if and
only if no basis of $E$ (for $M$) contains $e$.

\textbf{(b)} The element $e$ is said to be a \textit{coloop} (of $M$) if and
only if every basis of $E$ (for $M$) contains $e$.
\end{definition}

\begin{proposition}
\label{prop.loops.equiv}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
Let $e\in E$.

\textbf{(a)} The element $e$ is a loop (of $M$) if and only if $r_{M}\left(
e\right)  =0$.

\textbf{(b)} The element $e$ is a coloop (of $M$) if and only if $r_{M}\left(
E\right)  =r_{M}\left(  E\setminus e\right)  +1$.

\textbf{(c)} If $r_{M}\left(  E\setminus e\right)  \neq r_{M}\left(  E\right)
$, then the element $e$ is a coloop.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.loops.equiv}.]\textbf{(a)} $\Longrightarrow:$
Assume that the element $e$ is a loop. We need to show that $r_{M}\left(
e\right)  =0$.

Let $Z$ be a basis of $\left\{  e\right\}  $ (for $M$). Thus, $r_{M}\left(
\left\{  e\right\}  \right)  =\left\vert Z\right\vert $.

The set $Z$ is a basis of $\left\{  e\right\}  $, thus an independent set.
Clearly, $Z\subseteq E$. Thus, the independent set $Z$ can be extended to a
basis of $E$. In other words, there exists a basis $W$ of $E$ such that
$Z\subseteq W$. Consider this $W$.

The element $e$ is a loop. Thus, no basis of $E$ contains $e$ (by the
definition of a \textquotedblleft loop\textquotedblright). In particular, $W$
does not contain $e$ (since $W$ is a basis of $E$). Hence, $Z$ does not
contain $e$ (since $Z\subseteq W$). Combining this with $Z\subseteq\left\{
e\right\}  $, we obtain $Z\subseteq\left\{  e\right\}  \setminus
e=\varnothing$. Hence, $Z=\varnothing$ and thus $\left\vert Z\right\vert =0$.
Now, $r_{M}\left(  e\right)  =r_{M}\left(  \left\{  e\right\}  \right)
=\left\vert Z\right\vert =0$. This finishes the proof of the $\Longrightarrow$
direction of Proposition \ref{prop.loops.equiv} \textbf{(a)}.

$\Longleftarrow:$ Assume that $r_{M}\left(  e\right)  =0$. We need to show
that the element $e$ is a loop.

Let $B$ be a basis of $E$ (for $M$) such that $e\in B$. From $e\in B$, we
obtain $\left\{  e\right\}  \subseteq B$. The set $B$ is independent (since it
is a basis of $E$). Hence, the set $\left\{  e\right\}  $ is independent
(since $\left\{  e\right\}  \subseteq B$). Since $\left\{  e\right\}
\subseteq\left\{  e\right\}  $, this entails that $\left\vert \left\{
e\right\}  \right\vert \leq r_{M}\left(  \left\{  e\right\}  \right)  $ (by
Proposition \ref{prop.basis.basics} \textbf{(e)}, applied to $U=\left\{
e\right\}  $ and $S=\left\{  e\right\}  $). Hence, $r_{M}\left(  \left\{
e\right\}  \right)  \geq\left\vert \left\{  e\right\}  \right\vert =1$. This
contradicts $r_{M}\left(  \left\{  e\right\}  \right)  =r_{M}\left(  e\right)
=0$.

Now, let us forget that we fixed $B$. We thus have found a contradiction for
every basis $B$ of $E$ satisfying $e\in B$. Hence, there exists no basis $B$
of $E$ satisfying $e\in B$. In other words, no basis of $E$ contains $e$. In
other words, $e$ is a loop (by the definition of a \textquotedblleft
loop\textquotedblright). This proves the $\Longleftarrow$ direction of
Proposition \ref{prop.loops.equiv} \textbf{(a)}.

\textbf{(c)} Assume that $r_{M}\left(  E\setminus e\right)  \neq r_{M}\left(
E\right)  $. We need to show that the element $e$ is a coloop.

From $E\setminus e\subseteq E$, we obtain $r_{M}\left(  E\setminus e\right)
\leq r_{M}\left(  E\right)  $. Combined with $r_{M}\left(  E\setminus
e\right)  \neq r_{M}\left(  E\right)  $, this yields $r_{M}\left(  E\setminus
e\right)  <r_{M}\left(  E\right)  $.

Let $B$ be a basis of $E$. Thus, $r_{M}\left(  E\right)  =\left\vert
B\right\vert $.

Assume (for the sake of contradiction) that $e\notin B$. Thus, $B\subseteq
E\setminus e$. But $B$ is a basis of $E$ and thus an independent subset.
Hence, from $B\subseteq E\setminus e$, we obtain $\left\vert B\right\vert \leq
r_{M}\left(  E\setminus e\right)  $ (by Proposition \ref{prop.basis.basics}
\textbf{(e)}, applied to $U=B$ and $S=E\setminus e$). Thus,
\[
\left\vert B\right\vert \leq r_{M}\left(  E\setminus e\right)  <r_{M}\left(
E\right)  =\left\vert B\right\vert ,
\]
which is absurd. This contradiction shows that our assumption (that $e\notin
B$) was wrong. Hence, we must have $e\in B$.

Now, let us forget that we fixed $B$. We thus have shown that $e\in B$ for
every basis $B$ of $E$. In other words, every basis of $E$ (for $M$) contains
$e$. In other words, $e$ is a coloop (by the definition of a \textquotedblleft
coloop\textquotedblright). This proves Proposition \ref{prop.loops.equiv}
\textbf{(c)}.

\textbf{(b)} $\Longrightarrow:$ Assume that the element $e$ is a coloop. We
need to show that $r_{M}\left(  E\right)  =r_{M}\left(  E\setminus e\right)
+1$.

Pick a basis $B$ of $E$ (for $M$). Thus, $r_{M}\left(  E\right)  =\left\vert
B\right\vert $.

Recall that $e$ is a coloop. In other words, every basis of $E$ (for $M$)
contains $e$ (by the definition of a \textquotedblleft
coloop\textquotedblright).

But $B$ is a basis of $E$, and thus an independent set. Hence, $B\setminus e$
is also an independent set (since $B\setminus e\subseteq B$). Since
$\underbrace{B}_{\subseteq E}\setminus e\subseteq E\setminus e$, we thus have
$\left\vert B\setminus e\right\vert \leq r_{M}\left(  E\setminus e\right)  $
(by Proposition \ref{prop.basis.basics} \textbf{(e)}, applied to $U=B\setminus
e$ and $S=E\setminus e$). Thus, $r_{M}\left(  E\setminus e\right)
\geq\left\vert B\setminus e\right\vert \geq\underbrace{\left\vert B\right\vert
}_{=r_{M}\left(  E\right)  }-1=r_{M}\left(  E\right)  -1$.

Now, pick any basis $C$ of $E\setminus e$ (for $M$). Thus, $r_{M}\left(
E\setminus e\right)  =\left\vert C\right\vert $.

The set $C$ is a basis of $E\setminus e$, thus an independent set. Hence, we
can extend $C$ to a basis of $E$ (according to Proposition
\ref{prop.basis.basics} \textbf{(b)}). In other words, there exists a basis
$D$ of $E$ such that $C\subseteq D$. Pick such a $D$. Since $D$ is a basis of
$E$, we have $r_{M}\left(  E\right)  =\left\vert D\right\vert $. Since $D$ is
a basis of $E$, we have $e\in D$ (since every basis of $E$ contains $e$). But
$e\notin C$ (since $C\subseteq E\setminus e$). Hence, $C\neq D$ (since
$e\notin C$ but $e\in D$). Combined with $C\subseteq D$, this entails
$\left\vert C\right\vert <\left\vert D\right\vert $. Hence, $r_{M}\left(
E\setminus e\right)  =\left\vert C\right\vert <\left\vert D\right\vert
=r_{M}\left(  E\right)  $. In other words, $r_{M}\left(  E\setminus e\right)
\leq r_{M}\left(  E\right)  -1$. Combined with $r_{M}\left(  E\setminus
e\right)  \geq r_{M}\left(  E\right)  -1$, this yields $r_{M}\left(
E\setminus e\right)  =r_{M}\left(  E\right)  -1$. In other words,
$r_{M}\left(  E\right)  =r_{M}\left(  E\setminus e\right)  +1$. This proves
the $\Longrightarrow$ direction of Proposition \ref{prop.loops.equiv}
\textbf{(b)}.

$\Longleftarrow:$ Assume that $r_{M}\left(  E\right)  =r_{M}\left(  E\setminus
e\right)  +1$. We must show that the element $e$ is a coloop.

From $r_{M}\left(  E\right)  =r_{M}\left(  E\setminus e\right)  +1>r_{M}%
\left(  E\setminus e\right)  $, we have $r_{M}\left(  E\setminus e\right)
\neq r_{M}\left(  E\right)  $. Hence, $e$ is a coloop (by
\ref{prop.loops.equiv} \textbf{(c)}). The $\Longleftarrow$ direction of
Proposition \ref{prop.loops.equiv} \textbf{(b)} is thus proven.
\end{proof}

\begin{proposition}
\label{prop.loops.basics}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
Let $e\in E$.

\textbf{(a)} If $e$ is a loop, then $r_{M}\left(  S\cup e\right)
=r_{M}\left(  S\right)  $ for every $S\in\mathcal{P}\left(  E\right)  $.

\textbf{(b)} If $e$ is a coloop, then $r_{M}\left(  S\cup e\right)
=r_{M}\left(  S\right)  +1$ for every $S\in\mathcal{P}\left(  E\right)  $
satisfying $e\notin S$.

\textbf{(c)} If $e$ is a loop, then $n_{M}\left(  S\cup e\right)
=n_{M}\left(  S\right)  +1$ for every $S\in\mathcal{P}\left(  E\right)  $
satisfying $e\notin S$.

\textbf{(d)} If $e$ is a coloop, then $n_{M}\left(  S\cup e\right)
=n_{M}\left(  S\right)  $ for every $S\in\mathcal{P}\left(  E\right)  $.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.loops.basics}.]\textbf{(a)} Assume that $e$ is
a loop. Let $S\in\mathcal{P}\left(  E\right)  $.

Pick a basis $X$ of $S\cup e$ (for $M$). Then, $r_{M}\left(  S\cup e\right)
=\left\vert X\right\vert $.

The set $X$ is a basis of $S\cup e$, and thus is independent.

The element $e$ is a loop. Thus, $r_{M}\left(  e\right)  =0$ (by Proposition
\ref{prop.loops.equiv} \textbf{(a)}).

Assume (for the sake of contradiction) that $e\in X$. Then, $\left\{
e\right\}  \subseteq X$, so that $\left\{  e\right\}  $ is an independent set
(since $X$ is an independent set). Hence, Proposition \ref{prop.basis.basics}
\textbf{(e)} (applied to $\left\{  e\right\}  $ and $\left\{  e\right\}  $
instead of $S$ and $U$) shows that $\left\vert \left\{  e\right\}  \right\vert
\leq r_{M}\left(  \left\{  e\right\}  \right)  $. Thus, $r_{M}\left(  \left\{
e\right\}  \right)  \geq\left\vert \left\{  e\right\}  \right\vert =1$. This
contradicts $r_{M}\left(  \left\{  e\right\}  \right)  =r_{M}\left(  e\right)
=0$.

This contradiction shows that our assumption (that $e\in X$) was wrong. In
other words, we have $e\notin X$. Hence, $X\subseteq\left(  S\cup e\right)
\setminus e\subseteq S$. Thus, Proposition \ref{prop.basis.basics}
\textbf{(e)} (applied to $U=X$) shows that $\left\vert X\right\vert \leq
r_{M}\left(  S\right)  $. But $S\subseteq S\cup e$ shows that $r_{M}\left(
S\right)  \leq r_{M}\left(  S\cup e\right)  =\left\vert X\right\vert $.
Combining this with $\left\vert X\right\vert \leq r_{M}\left(  S\right)  $, we
obtain $\left\vert X\right\vert =r_{M}\left(  S\right)  $. Hence,
$r_{M}\left(  S\cup e\right)  =\left\vert X\right\vert =r_{M}\left(  S\right)
$. This proves Proposition \ref{prop.loops.basics} \textbf{(a)}.

\textbf{(b)} Assume that $e$ is a coloop. Let $S\in\mathcal{P}\left(
E\right)  $ be such that $e\notin S$.

The element $e$ is a coloop. Thus, $r_{M}\left(  E\right)  =r_{M}\left(
E\setminus e\right)  +1$ (according to Proposition \ref{prop.loops.equiv}
\textbf{(b)}).

Applying (\ref{eq.prop.nullity.monotone.b.eq}) to $T=S\cup e$, we obtain
$n_{M}\left(  S\right)  \leq n_{M}\left(  S\cup e\right)  $. Since
$n_{M}\left(  S\right)  =\left\vert S\right\vert -r_{M}\left(  S\right)  $ and
$n_{M}\left(  S\cup e\right)  =\left\vert S\cup e\right\vert -r_{M}\left(
S\cup e\right)  $ (by the definition of $n_{M}\left(  S\cup e\right)  $), this
rewrites as $\left\vert S\right\vert -r_{M}\left(  S\right)  \leq\left\vert
S\cup e\right\vert -r_{M}\left(  S\cup e\right)  $. Hence,%
\begin{align}
r_{M}\left(  S\right)   &  \leq\left\vert S\right\vert -\left(
\underbrace{\left\vert S\cup e\right\vert }_{\substack{=\left\vert
S\right\vert +1\\\text{(since }e\notin S\text{)}}}-r_{M}\left(  S\cup
e\right)  \right)  =\left\vert S\right\vert -\left(  \left\vert S\right\vert
+1-r_{M}\left(  S\cup e\right)  \right) \nonumber\\
&  =r_{M}\left(  S\cup e\right)  -1. \label{pf.prop.loops.basics.b.1}%
\end{align}


On the other hand, let us pick a basis $X$ of $S\cup e$ (for $M$). Then,
$r_{M}\left(  S\cup e\right)  =\left\vert X\right\vert $.

The set $X$ is a basis of $S\cup e$, and thus is independent. Also,
$X\subseteq E$. Hence, the independent set $X$ can be extended to a basis of
$E$. In other words, there exists a basis $Z$ of $E$ such that $X\subseteq Z$.
Consider this $Z$.

Since $Z$ is a basis of $E$, we have $r_{M}\left(  E\right)  =\left\vert
Z\right\vert $.

The set $Z$ is independent (since it is a basis of $E$). If we had $Z\subseteq
E\setminus e$, then we would have $\left\vert Z\right\vert \leq r_{M}\left(
E\setminus e\right)  $ (by Proposition \ref{prop.basis.basics} \textbf{(e)},
applied to $Z$ and $E\setminus e$ instead of $U$ and $S$), which would
contradict $\left\vert Z\right\vert =r_{M}\left(  E\right)  =r_{M}\left(
E\setminus e\right)  +1>r_{M}\left(  E\setminus e\right)  $. Hence, we cannot
have $Z\subseteq E\setminus e$. In other words, we must have $e\in Z$.

From $X\subseteq Z$ and $e\in Z$, we obtain $X\cup e\subseteq Z$. Thus, the
set $X\cup e$ is independent (since $Z$ is independent). From $\underbrace{X}%
_{\subseteq S\cup e}\cup e\subseteq S\cup e\cup e=S\cup e$, we therefore
obtain $\left\vert X\cup e\right\vert \leq r_{M}\left(  S\cup e\right)  $ (by
Proposition \ref{prop.basis.basics} \textbf{(e)}, applied to $X\cup e$ and
$S\cup e$ instead of $U$ and $S$).

Now, $\left\vert X\cup e\right\vert \leq r_{M}\left(  S\cup e\right)
=\left\vert X\right\vert $. Combined with $\left\vert X\right\vert
\leq\left\vert X\cup e\right\vert $ (since $X\subseteq X\cup e$), this shows
that $\left\vert X\cup e\right\vert =\left\vert X\right\vert $. Hence, $e\in
X$.

From $X\subseteq S\cup e$, we obtain $X\setminus e\subseteq S$. Also,
$X\setminus e$ is independent (since $X$ is independent, and since $X\setminus
e\subseteq X$). Hence, $X\setminus e$ is an independent subset of $S$.
Therefore, $\left\vert X\setminus e\right\vert \leq r_{M}\left(  S\right)  $
(by Proposition \ref{prop.basis.basics} \textbf{(e)}, applied to $Z$ and
$E\setminus e$ instead of $U$ and $S$). Thus, $r_{M}\left(  S\right)
\geq\left\vert X\setminus e\right\vert =\left\vert X\right\vert -1$ (since
$e\in X$). Since $r_{M}\left(  S\cup e\right)  =\left\vert X\right\vert $,
this rewrites as $r_{M}\left(  S\right)  \geq r_{M}\left(  S\cup e\right)
-1$. Combining this with (\ref{pf.prop.loops.basics.b.1}), we obtain
$r_{M}\left(  S\right)  =r_{M}\left(  S\cup e\right)  -1$. In other words,
$r_{M}\left(  S\cup e\right)  =r_{M}\left(  S\right)  +1$. This proves
Proposition \ref{prop.loops.basics} \textbf{(b)}.

\textbf{(c)} Assume that $e$ is a loop. Let $S\in\mathcal{P}\left(  E\right)
$ be such that $e\notin S$.

The definition of $n_{M}\left(  S\right)  $ shows that $n_{M}\left(  S\right)
=\left\vert S\right\vert -r_{M}\left(  S\right)  $.

The definition of $n_{M}\left(  S\cup e\right)  $ shows that
\begin{align*}
n_{M}\left(  S\cup e\right)   &  =\underbrace{\left\vert S\cup e\right\vert
}_{\substack{=\left\vert S\right\vert +1\\\text{(since }e\notin S\text{)}%
}}-\underbrace{r_{M}\left(  S\cup e\right)  }_{\substack{=r_{M}\left(
S\right)  \\\text{(by Proposition \ref{prop.loops.basics} \textbf{(a)})}%
}}=\left\vert S\right\vert +1-r_{M}\left(  S\right) \\
&  =\underbrace{\left\vert S\right\vert -r_{M}\left(  S\right)  }%
_{=n_{M}\left(  S\right)  }+1=n_{M}\left(  S\right)  +1.
\end{align*}
This proves Proposition \ref{prop.loops.basics} \textbf{(c)}.

\textbf{(d)} Assume that $e$ is a coloop. Let $S\in\mathcal{P}\left(
E\right)  $. We need to show that $n_{M}\left(  S\cup e\right)  =n_{M}\left(
S\right)  $. If $S\cup e=S$, then this is obvious. Hence, for the rest of this
proof, we WLOG assume that $S\cup e\neq S$. Thus, $e\notin S$.

The definition of $n_{M}\left(  S\right)  $ shows that $n_{M}\left(  S\right)
=\left\vert S\right\vert -r_{M}\left(  S\right)  $.

The definition of $n_{M}\left(  S\cup e\right)  $ shows that
\begin{align*}
n_{M}\left(  S\cup e\right)   &  =\underbrace{\left\vert S\cup e\right\vert
}_{\substack{=\left\vert S\right\vert +1\\\text{(since }e\notin S\text{)}%
}}-\underbrace{r_{M}\left(  S\cup e\right)  }_{\substack{=r_{M}\left(
S\right)  +1\\\text{(by Proposition \ref{prop.loops.basics} \textbf{(b)})}%
}}=\left\vert S\right\vert +1-\left(  r_{M}\left(  S\right)  +1\right) \\
&  =\left\vert S\right\vert -r_{M}\left(  S\right)  =n_{M}\left(  S\right)  .
\end{align*}
This proves Proposition \ref{prop.loops.basics} \textbf{(d)}.
\end{proof}

\begin{definition}
\label{def.basis-of-M}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. A
\textit{basis} of $M$ will mean a basis of $E$ (for $M$). We let
$\mathcal{B}\left(  M\right)  $ denote the set of all bases of $M$. It is
well-known that $M$ can be uniquely reconstructed from $\mathcal{B}\left(
M\right)  $.
\end{definition}

\begin{proposition}
\label{prop.basis-of-M.form}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. We have
\[
\mathcal{B}\left(  M\right)  =\left\{  B\in\mathcal{I}\ \mid\ \left\vert
B\right\vert =r_{M}\left(  E\right)  \right\}  .
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.basis-of-M.form}.]Let $Z\in\mathcal{B}\left(
M\right)  $. Thus, $Z$ is a basis of $M$ (since $\mathcal{B}\left(  M\right)
$ is the set of all bases of $M$). In other words, $Z$ is a basis of $E$ (for
$M$) (by the definition of a \textquotedblleft basis of $M$\textquotedblright%
). In other words, $Z$ is a maximum-size independent (for $M$) subset of $E$.
Thus, $Z$ is an independent subset of $E$. In other words, $Z\in\mathcal{I}$.
Also, $r_{M}\left(  E\right)  =\left\vert Z\right\vert $ (since Z is a basis
of $E$). Combined with $Z\in\mathcal{I}$, this yields $Z\in\left\{
B\in\mathcal{I}\ \mid\ \left\vert B\right\vert =r_{M}\left(  E\right)
\right\}  $.

Let us now forget that we fixed $Z$. We thus have shown that \newline%
$Z\in\left\{  B\in\mathcal{I}\ \mid\ \left\vert B\right\vert =r_{M}\left(
E\right)  \right\}  $ for every $Z\in\mathcal{B}\left(  M\right)  $. In other
words,%
\begin{equation}
\mathcal{B}\left(  M\right)  \subseteq\left\{  B\in\mathcal{I}\ \mid
\ \left\vert B\right\vert =r_{M}\left(  E\right)  \right\}  .
\label{pf.prop.basis-of-M.form.1}%
\end{equation}


On the other hand, let $Y\in\left\{  B\in\mathcal{I}\ \mid\ \left\vert
B\right\vert =r_{M}\left(  E\right)  \right\}  $. Thus, $Y\in\mathcal{I}$ is
such that $\left\vert Y\right\vert =r_{M}\left(  E\right)  $. The set $Y$ is
independent (since $Y\in\mathcal{I}$). Hence, then there exists a basis $T$ of
$E$ such that $Y\subseteq T$ (by Proposition \ref{prop.basis.basics}
\textbf{(b)}, applied to $S=E$ and $U=Y$). Consider this $T$. We have
$\left\vert T\right\vert =r_{M}\left(  E\right)  $ (since $T$ is a basis of
$E$) and thus $\left\vert T\right\vert =r_{M}\left(  E\right)  =\left\vert
Y\right\vert $. Combined with $Y\subseteq T$, this yields $Y=T$. Thus, $Y$ is
a basis of $E$ (since $T$ is a basis of $E$). In other words, $Y$ is a basis
of $M$ (by the definition of a \textquotedblleft basis of $M$%
\textquotedblright). In other words, $Y\in\mathcal{B}\left(  M\right)  $
(since $\mathcal{B}\left(  M\right)  $ is the set of all bases of $M$).

Let us now forget that we fixed $Y$. We thus have shown that $Y\in
\mathcal{B}\left(  M\right)  $ for every $Y\in\left\{  B\in\mathcal{I}%
\ \mid\ \left\vert B\right\vert =r_{M}\left(  E\right)  \right\}  $. In other
words,%
\[
\left\{  B\in\mathcal{I}\ \mid\ \left\vert B\right\vert =r_{M}\left(
E\right)  \right\}  \subseteq\mathcal{B}\left(  M\right)  .
\]
Combined with (\ref{pf.prop.basis-of-M.form.1}), this yields $\mathcal{B}%
\left(  M\right)  =\left\{  B\in\mathcal{I}\ \mid\ \left\vert B\right\vert
=r_{M}\left(  E\right)  \right\}  $. Proposition \ref{prop.basis-of-M.form} is
thus proven.
\end{proof}

Next, let us define the dual matroid of a matroid (following \cite[Definition
3.32]{Martin15}):

\begin{definition}
\label{def.dual-matroid}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
There exists a unique matroid $N=\left(  E,\mathcal{J}\right)  $ with ground
set $E$ such that $\mathcal{B}\left(  N\right)  =\left\{  E\setminus
B\ \mid\ B\in\mathcal{B}\left(  M\right)  \right\}  $. This matroid $N$ is
called the \textit{dual matroid} of $M$, and is denoted by $M^{\ast}$. For
every $S\in\mathcal{P}\left(  E\right)  $, we have%
\begin{equation}
r_{M^{\ast}}\left(  S\right)  =\left\vert S\right\vert +r_{M}\left(
E\setminus S\right)  -r_{M}\left(  E\right)  \label{eq.def.dual-matroid.rank}%
\end{equation}
(by \cite[Theorem 10.3]{Schrij13}). It is furthermore easy to see that
$\left(  M^{\ast}\right)  ^{\ast}=M$.
\end{definition}

\begin{proposition}
\label{prop.dual-loop}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Let
$e\in E$. Then, $e$ is a loop of $M$ if and only if $e$ is a coloop of
$M^{\ast}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.dual-loop}.]The equality
(\ref{eq.def.dual-matroid.rank}) (applied to $S=E$) shows that%
\begin{align*}
r_{M^{\ast}}\left(  E\right)   &  =\left\vert E\right\vert +r_{M}\left(
\underbrace{E\setminus E}_{=\varnothing}\right)  -r_{M}\left(  E\right)
=\left\vert E\right\vert +\underbrace{r_{M}\left(  \varnothing\right)  }%
_{=0}-r_{M}\left(  E\right) \\
&  =\left\vert E\right\vert -r_{M}\left(  E\right)  .
\end{align*}
Also, (\ref{eq.def.dual-matroid.rank}) (applied to $S=E\setminus e$) shows
that%
\begin{align*}
r_{M^{\ast}}\left(  E\setminus e\right)   &  =\underbrace{\left\vert
E\setminus e\right\vert }_{\substack{=\left\vert E\right\vert -1\\\text{(since
}e\in E\text{)}}}+r_{M}\left(  \underbrace{E\setminus\left(  E\setminus
e\right)  }_{=\left\{  e\right\}  }\right)  -r_{M}\left(  E\right)
=\left\vert E\right\vert -1+\underbrace{r_{M}\left(  \left\{  e\right\}
\right)  }_{=r_{M}\left(  e\right)  }-r_{M}\left(  E\right) \\
&  =\left\vert E\right\vert -1+r_{M}\left(  e\right)  -r_{M}\left(  E\right)
.
\end{align*}


Write the matroid $M^{\ast}$ in the form $M^{\ast}=\left(  E,\mathcal{J}%
\right)  $. Proposition \ref{prop.loops.equiv} \textbf{(b)} (applied to
$M^{\ast}$ and $\mathcal{J}$ instead of $M$ and $\mathcal{I}$) shows that $e$
is a coloop of $M^{\ast}$ if and only if $r_{M^{\ast}}\left(  E\right)
=r_{M^{\ast}}\left(  E\setminus e\right)  +1$. Hence, we have the following
chain of logical equivalences:%
\begin{align*}
&  \ \left(  e\text{ is a coloop of }M^{\ast}\right) \\
&  \Longleftrightarrow\ \left(  \underbrace{r_{M^{\ast}}\left(  E\right)
}_{=\left\vert E\right\vert -r_{M}\left(  E\right)  }=\underbrace{r_{M^{\ast}%
}\left(  E\setminus e\right)  }_{=\left\vert E\right\vert -1+r_{M}\left(
e\right)  -r_{M}\left(  E\right)  }+1\right) \\
&  \Longleftrightarrow\ \left(  \left\vert E\right\vert -r_{M}\left(
E\right)  =\left\vert E\right\vert -1+r_{M}\left(  e\right)  -r_{M}\left(
E\right)  +1\right) \\
&  \Longleftrightarrow\ \left(  r_{M}\left(  e\right)  =0\right)
\ \Longleftrightarrow\ \left(  e\text{ is a loop of }M\right)
\end{align*}
(by Proposition \ref{prop.loops.equiv} \textbf{(a)}). This proves Proposition
\ref{prop.dual-loop}.
\end{proof}

\begin{definition}
\label{def.restriction}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
Let $Y$ be a subset of $E$. Then, the pair $\left(  Y,\mathcal{I}%
\cap\mathcal{P}\left(  Y\right)  \right)  $ is a matroid with ground set $Y$.
This matroid is called the \textit{restriction} of $M$ to $Y$, and is denoted
by $M\mid_{Y}$.
\end{definition}

\begin{definition}
\label{def.delcon}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Let $Z$
be a subset of $E$.

\textbf{(a)} The \textit{deletion} of $Z$ from $M$ is defined to be the
matroid $M\mid_{E\setminus Z}$ (that is, the restriction of $M$ to $E\setminus
Z$). This is a matroid with ground set $Z$, and is denoted by $M\setminus Z$.

\textbf{(b)} The \textit{contraction} of $Z$ in $M$ is defined to be the
matroid $\left(  M^{\ast}\setminus Z\right)  ^{\ast}$. This is a matroid with
ground set $Z$, and is denoted by $M/Z$.
\end{definition}

We shall first show formulas for ranks in $M\setminus Z$ and $M/Z$:

\begin{proposition}
\label{prop.delcon.rank}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
Let $Z$ be a subset of $E$. Let $S\in\mathcal{P}\left(  E\setminus Z\right)  $.

\textbf{(a)} We have $r_{M\setminus Z}\left(  S\right)  =r_{M}\left(
S\right)  $.

\textbf{(b)} We have $r_{M/Z}\left(  S\right)  =r_{M}\left(  S\cup Z\right)
-r_{M}\left(  Z\right)  $.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.delcon.rank}.]\textbf{(a)} We have
$S\in\mathcal{P}\left(  E\setminus Z\right)  $, thus $S\subseteq E\setminus
Z\subseteq E$. Thus,
\begin{equation}
r_{M}\left(  S\right)  =\max\left\{  \left\vert Y\right\vert \ \mid
\ Y\in\mathcal{I}\text{ and }Y\subseteq S\right\}  .
\label{pf.prop.delcon.rank.a.1}%
\end{equation}
(This is merely the equality (\ref{eq.def.rank.def}), with the index $Z$
renamed as $Y$.)

But the definition of $M\setminus Z$ yields $M\setminus Z=M\mid_{E\setminus
Z}=\left(  E\setminus Z,\mathcal{I}\cap\mathcal{P}\left(  E\setminus Z\right)
\right)  $ (by the definition of $M\mid_{E\setminus Z}$). Hence, we can apply
(\ref{pf.prop.delcon.rank.a.1}) to $M\setminus Z$, $E\setminus Z$ and
$\mathcal{I}\cap\mathcal{P}\left(  E\setminus Z\right)  $ instead of $M$, $E$
and $\mathcal{I}$ (since $S\subseteq E\setminus Z$). We thus obtain%
\begin{equation}
r_{M\setminus Z}\left(  S\right)  =\max\left\{  \left\vert Y\right\vert
\ \mid\ Y\in\mathcal{I}\cap\mathcal{P}\left(  E\setminus Z\right)  \text{ and
}Y\subseteq S\right\}  . \label{pf.prop.delcon.rank.a.2}%
\end{equation}


For any subset $Y$ of $S$, the statements $Y\in\mathcal{I}$ and $Y\in
\mathcal{I}\cap\mathcal{P}\left(  E\setminus Z\right)  $ are
equivalent\footnote{\textit{Proof.} Let $Y$ be a subset of $S$. We need to
show that the statements $Y\in\mathcal{I}$ and $Y\in\mathcal{I}\cap
\mathcal{P}\left(  E\setminus Z\right)  $ are equivalent. Since the statement
$Y\in\mathcal{I}\cap\mathcal{P}\left(  E\setminus Z\right)  $ clearly implies
the statement $Y\in\mathcal{I}$, we only need to show that the statement
$Y\in\mathcal{I}$ implies the statement $Y\in\mathcal{I}\cap\mathcal{P}\left(
E\setminus Z\right)  $. Let us do this now.
\par
Let us assume that $Y\in\mathcal{I}$. But $Y\subseteq S\subseteq E\setminus
Z$, so that $Y\in\mathcal{P}\left(  E\setminus Z\right)  $. Combined with
$Y\in\mathcal{I}$, this entails $Y\in\mathcal{I}\cap\mathcal{P}\left(
E\setminus Z\right)  $. Now, let us forget that we assumed that $Y\in
\mathcal{I}$. We thus have shown that the statement $Y\in\mathcal{I}$ implies
the statement $Y\in\mathcal{I}\cap\mathcal{P}\left(  E\setminus Z\right)  $.
This completes our proof.}. Thus, (\ref{pf.prop.delcon.rank.a.1}) becomes%
\begin{align*}
r_{M}\left(  S\right)   &  =\max\left\{  \left\vert Y\right\vert
\ \mid\ \underbrace{Y\in\mathcal{I}}_{\substack{\text{this is equivalent
to}\\Y\in\mathcal{I}\cap\mathcal{P}\left(  E\setminus Z\right)  }}\text{ and
}Y\subseteq S\right\} \\
&  =\max\left\{  \left\vert Y\right\vert \ \mid\ Y\in\mathcal{I}%
\cap\mathcal{P}\left(  E\setminus Z\right)  \text{ and }Y\subseteq S\right\}
=r_{M\setminus Z}\left(  S\right)
\end{align*}
(by (\ref{pf.prop.delcon.rank.a.2})). This proves Proposition
\ref{prop.delcon.rank} \textbf{(a)}.

\textbf{(b)} We have $S\in\mathcal{P}\left(  E\setminus Z\right)  $, thus
$S\subseteq E\setminus Z\subseteq E$. Combined with $Z\subseteq E$, this
yields $Z\cup S\subseteq E$. From $S\subseteq E\setminus Z$, we obtain
$\left\vert \left(  E\setminus Z\right)  \setminus S\right\vert =\left\vert
E\setminus Z\right\vert -\left\vert S\right\vert $. Hence, $\left\vert
\underbrace{E\setminus\left(  Z\cup S\right)  }_{=\left(  E\setminus Z\right)
\setminus S}\right\vert =\left\vert \left(  E\setminus Z\right)  \setminus
S\right\vert =\left\vert E\setminus Z\right\vert -\left\vert S\right\vert $.

Now, (\ref{eq.def.dual-matroid.rank}) (applied to $E\setminus\left(  Z\cup
S\right)  $ instead of $S$) shows that%
\begin{align}
r_{M^{\ast}}\left(  E\setminus\left(  Z\cup S\right)  \right)   &
=\underbrace{\left\vert E\setminus\left(  Z\cup S\right)  \right\vert
}_{=\left\vert E\setminus Z\right\vert -\left\vert S\right\vert }+r_{M}\left(
\underbrace{E\setminus\left(  E\setminus\left(  Z\cup S\right)  \right)
}_{\substack{=Z\cup S\\\text{(since }Z\cup S\subseteq E\text{)}}}\right)
-r_{M}\left(  E\right) \nonumber\\
&  =\left\vert E\setminus Z\right\vert -\left\vert S\right\vert +r_{M}\left(
Z\cup S\right)  -r_{M}\left(  E\right)  . \label{pf.prop.delcon.rank.b.1}%
\end{align}


The definition of $M/Z$ yields $M/Z=\left(  M^{\ast}\setminus Z\right)
^{\ast}$. The ground set of $\left(  M^{\ast}\setminus Z\right)  ^{\ast}$ is
the ground set of $M^{\ast}\setminus Z$, which is $E\setminus Z$ (since the
ground set of $M^{\ast}$ is $E$). Now, from $M/Z=\left(  M^{\ast}\setminus
Z\right)  ^{\ast}$, we obtain $r_{M/Z}\left(  S\right)  =r_{\left(  M^{\ast
}\setminus Z\right)  ^{\ast}}\left(  S\right)  $.

Let us write the matroid $M^{\ast}$ as $\left(  E,\mathcal{K}\right)  $.

But let us write the matroid $M^{\ast}\setminus Z$ as $\left(  E\setminus
Z,\mathcal{J}\right)  $. Then, (\ref{eq.def.dual-matroid.rank}) (applied to
$M^{\ast}\setminus Z$, $E\setminus Z$ and $\mathcal{J}$ instead of $M$, $E$
and $\mathcal{I}$) shows that%
\[
r_{\left(  M^{\ast}\setminus Z\right)  ^{\ast}}\left(  S\right)  =\left\vert
S\right\vert +r_{M^{\ast}\setminus Z}\left(  \left(  E\setminus Z\right)
\setminus S\right)  -r_{M^{\ast}\setminus Z}\left(  E\setminus Z\right)
\]
(since the ground set of $M^{\ast}\setminus Z$ is $E\setminus Z$). Hence,
\begin{align*}
r_{M/Z}\left(  S\right)   &  =r_{\left(  M^{\ast}\setminus Z\right)  ^{\ast}%
}\left(  S\right) \\
&  =\left\vert S\right\vert +\underbrace{r_{M^{\ast}\setminus Z}\left(
\left(  E\setminus Z\right)  \setminus S\right)  }_{\substack{=r_{M^{\ast}%
}\left(  \left(  E\setminus Z\right)  \setminus S\right)  \\\text{(by
Proposition \ref{prop.delcon.rank} \textbf{(a)}}\\\text{(applied to }M^{\ast
}\text{, }\mathcal{K}\text{ and }\left(  E\setminus Z\right)  \setminus
S\\\text{instead of }M\text{, }\mathcal{I}\text{ and }S\text{))}%
}}-\underbrace{r_{M^{\ast}\setminus Z}\left(  E\setminus Z\right)
}_{\substack{=r_{M^{\ast}}\left(  E\setminus Z\right)  \\\text{(by Proposition
\ref{prop.delcon.rank} \textbf{(a)}}\\\text{(applied to }M^{\ast}\text{,
}\mathcal{K}\text{ and }\left(  E\setminus Z\right)  \setminus
S\\\text{instead of }M\text{, }\mathcal{I}\text{ and }S\text{))}}}\\
&  =\left\vert S\right\vert +r_{M^{\ast}}\left(  \underbrace{\left(
E\setminus Z\right)  \setminus S}_{=E\setminus\left(  Z\cup S\right)
}\right)  -r_{M^{\ast}}\left(  E\setminus Z\right) \\
&  =\left\vert S\right\vert +\underbrace{r_{M^{\ast}}\left(  E\setminus\left(
Z\cup S\right)  \right)  }_{\substack{=\left\vert E\setminus Z\right\vert
-\left\vert S\right\vert +r_{M}\left(  Z\cup S\right)  -r_{M}\left(  E\right)
\\\text{(by (\ref{pf.prop.delcon.rank.b.1}))}}}-\underbrace{r_{M^{\ast}%
}\left(  E\setminus Z\right)  }_{\substack{=\left\vert E\setminus Z\right\vert
+r_{M}\left(  E\setminus\left(  E\setminus Z\right)  \right)  -r_{M}\left(
E\right)  \\\text{(by (\ref{eq.def.dual-matroid.rank})}\\\text{(applied to
}E\setminus Z\text{ instead of }S\text{))}}}\\
&  =\left\vert S\right\vert +\left(  \left\vert E\setminus Z\right\vert
-\left\vert S\right\vert +r_{M}\left(  Z\cup S\right)  -r_{M}\left(  E\right)
\right) \\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \left\vert E\setminus Z\right\vert
+r_{M}\left(  E\setminus\left(  E\setminus Z\right)  \right)  -r_{M}\left(
E\right)  \right) \\
&  =r_{M}\left(  \underbrace{Z\cup S}_{=S\cup Z}\right)  -r_{M}\left(
\underbrace{E\setminus\left(  E\setminus Z\right)  }%
_{\substack{=Z\\\text{(since }Z\subseteq E\text{)}}}\right)  =r_{M}\left(
S\cup Z\right)  -r_{M}\left(  Z\right)  .
\end{align*}
This proves Proposition \ref{prop.delcon.rank} \textbf{(b)}.
\end{proof}

\begin{definition}
\label{def.delcon.e}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Let
$e\in E$.

\textbf{(a)} We denote the matroid $M\setminus\left\{  e\right\}  $ by
$M\setminus e$. This is a matroid with ground set $E\setminus\left\{
e\right\}  =E\setminus e$.

\textbf{(b)} We denote the matroid $M/\left\{  e\right\}  $ by $M/e$. This is
a matroid with ground set $E\setminus\left\{  e\right\}  =E\setminus e$.
\end{definition}

\begin{proposition}
\label{prop.delcon.del-e-bases}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. Let $e\in E$. Assume that $e$ is not a coloop of $M$. Then,%
\[
\mathcal{B}\left(  M\setminus e\right)  =\left\{  B\in\mathcal{B}\left(
M\right)  \ \mid\ e\notin B\right\}  .
\]

\end{proposition}

Proposition \ref{prop.delcon.del-e-bases} shows that our definition of
$M\setminus e$ (in the case when $e$ is not a coloop of $M$) is equivalent to
the definition in \cite[Definition 3.36]{Martin15}.

\begin{proof}
[Proof of Proposition \ref{prop.delcon.del-e-bases}.]The definition of
$M\setminus e$ shows that%
\[
M\setminus e=M\setminus\left\{  e\right\}  =M\mid_{E\setminus\left\{
e\right\}  }=\left(  E\setminus\left\{  e\right\}  ,\mathcal{I}\cap
\mathcal{P}\left(  E\setminus\left\{  e\right\}  \right)  \right)  =\left(
E\setminus e,\mathcal{I}\cap\mathcal{P}\left(  E\setminus e\right)  \right)
.
\]
Hence, Proposition \ref{prop.basis-of-M.form} (applied to $M\setminus e$,
$E\setminus e$ and $\mathcal{I}\cap\mathcal{P}\left(  E\setminus e\right)  $
instead of $M$, $E$ and $\mathcal{I}$) shows that%
\[
\mathcal{B}\left(  M\setminus e\right)  =\left\{  B\in\mathcal{I}%
\cap\mathcal{P}\left(  E\setminus e\right)  \ \mid\ \left\vert B\right\vert
=r_{M\setminus e}\left(  E\setminus e\right)  \right\}  .
\]


But $E\setminus e=E\setminus\left\{  e\right\}  \in\mathcal{P}\left(
E\setminus\left\{  e\right\}  \right)  $. Hence, Proposition
\ref{prop.delcon.rank} \textbf{(a)} (applied to $Z=\left\{  e\right\}  $ and
$S=E\setminus e$) shows that $r_{M\setminus\left\{  e\right\}  }\left(
E\setminus e\right)  =r_{M}\left(  E\setminus e\right)  $.

But if we had $r_{M}\left(  E\setminus e\right)  \neq r_{M}\left(  E\right)
$, then the element $e$ would be a coloop of $M$ (by Proposition
\ref{prop.loops.equiv} \textbf{(c)}), which would contradict the fact that $e$
is not a coloop of $M$. Hence, we cannot have $r_{M}\left(  E\setminus
e\right)  \neq r_{M}\left(  E\right)  $. In other words, we have $r_{M}\left(
E\setminus e\right)  =r_{M}\left(  E\right)  $. Hence, $r_{M\setminus\left\{
e\right\}  }\left(  E\setminus e\right)  =r_{M}\left(  E\setminus e\right)
=r_{M}\left(  E\right)  $-

Now,%
\begin{align*}
\mathcal{B}\left(  M\setminus e\right)   &  =\left\{  B\in\mathcal{I}%
\cap\mathcal{P}\left(  E\setminus e\right)  \ \mid\ \left\vert B\right\vert
=\underbrace{r_{M\setminus e}\left(  E\setminus e\right)  }_{=r_{M\setminus
\left\{  e\right\}  }\left(  E\setminus e\right)  =r_{M}\left(  E\right)
}\right\} \\
&  =\left\{  B\in\mathcal{I}\cap\mathcal{P}\left(  E\setminus e\right)
\ \mid\ \left\vert B\right\vert =r_{M}\left(  E\right)  \right\} \\
&  =\underbrace{\left\{  B\in\mathcal{I}\ \mid\ \left\vert B\right\vert
=r_{M}\left(  E\right)  \right\}  }_{\substack{=\mathcal{B}\left(  M\right)
\\\text{(by Proposition \ref{prop.basis-of-M.form})}}}\cap\mathcal{P}\left(
E\setminus e\right) \\
&  =\mathcal{B}\left(  M\right)  \cap\mathcal{P}\left(  E\setminus e\right)
=\left\{  B\in\mathcal{B}\left(  M\right)  \ \mid\ \underbrace{B\in
\mathcal{P}\left(  E\setminus e\right)  }_{\text{this is equivalent to
}B\subseteq E\setminus e}\right\} \\
&  =\left\{  B\in\mathcal{B}\left(  M\right)  \ \mid\ \underbrace{B\subseteq
E\setminus e}_{\text{this is equivalent to }e\notin B}\right\}  =\left\{
B\in\mathcal{B}\left(  M\right)  \ \mid\ e\notin B\right\}  .
\end{align*}
This proves Proposition \ref{prop.delcon.del-e-bases}.
\end{proof}

\begin{proposition}
\label{prop.delcon.con-e-bases}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. Let $e\in E$. Assume that $e$ is not a loop of $M$. Then,%
\[
\mathcal{B}\left(  M/e\right)  =\left\{  B\setminus e\ \mid\ B\in
\mathcal{B}\left(  M\right)  \text{ and }e\in B\right\}  .
\]

\end{proposition}

Proposition \ref{prop.delcon.con-e-bases} shows that our definition of $M/e$
(in the case when $e$ is not a loop of $M$) is equivalent to the definition in
\cite[Definition 3.36]{Martin15}.

\begin{proof}
[Proof of Proposition \ref{prop.delcon.con-e-bases}.]Proposition
\ref{prop.dual-loop} shows that $e$ is a loop of $M$ if and only if $e$ is a
coloop of $M^{\ast}$. Thus, $e$ is not a coloop of $M^{\ast}$ (since $e$ is
not a loop of $M$).

But the definition of $M^{\ast}$ shows that
\[
\mathcal{B}\left(  M^{\ast}\right)  =\left\{  E\setminus B\ \mid
\ B\in\mathcal{B}\left(  M\right)  \right\}  =\left\{  E\setminus
C\ \mid\ C\in\mathcal{B}\left(  M\right)  \right\}
\]
(here, we renamed the index $B$ as $C$).

Write the matroid $M^{\ast}$ as $\left(  E,\mathcal{K}\right)  $. Proposition
\ref{prop.delcon.del-e-bases} (applied to $M^{\ast}$ and $\mathcal{K}$ instead
of $M$ and $\mathcal{I}$) shows that%
\begin{align*}
\mathcal{B}\left(  M^{\ast}\setminus e\right)   &  =\left\{  B\in
\underbrace{\mathcal{B}\left(  M^{\ast}\right)  }_{=\left\{  E\setminus
C\ \mid\ C\in\mathcal{B}\left(  M\right)  \right\}  }\ \mid\ e\notin B\right\}
\\
&  =\left\{  B\in\left\{  E\setminus C\ \mid\ C\in\mathcal{B}\left(  M\right)
\right\}  \ \mid\ e\notin B\right\} \\
&  =\left\{  E\setminus C\ \mid\ C\in\mathcal{B}\left(  M\right)  \text{ and
}\underbrace{e\notin E\setminus C}_{\substack{\text{this is equivalent to
}e\in C\\\text{(since }e\in E\text{)}}}\right\} \\
&  =\left\{  E\setminus C\ \mid\ C\in\mathcal{B}\left(  M\right)  \text{ and
}e\in C\right\}  .
\end{align*}


On the other hand,
\begin{align*}
M/e  &  =M/\left\{  e\right\}  =\left(  \underbrace{M^{\ast}\setminus\left\{
e\right\}  }_{=M^{\ast}\setminus e}\right)  ^{\ast}\ \ \ \ \ \ \ \ \ \ \left(
\text{by the definition of }M/\left\{  e\right\}  \right) \\
&  =\left(  M^{\ast}\setminus e\right)  ^{\ast},
\end{align*}
so that%
\begin{align*}
\mathcal{B}\left(  M/e\right)   &  =\mathcal{B}\left(  \left(  M^{\ast
}\setminus e\right)  ^{\ast}\right)  =\left\{  \left(  E\setminus e\right)
\setminus B\ \mid\ B\in\underbrace{\mathcal{B}\left(  M^{\ast}\setminus
e\right)  }_{=\left\{  E\setminus C\ \mid\ C\in\mathcal{B}\left(  M\right)
\text{ and }e\in C\right\}  }\right\} \\
&  =\left\{  \left(  E\setminus e\right)  \setminus B\ \mid\ B\in\left\{
E\setminus C\ \mid\ C\in\mathcal{B}\left(  M\right)  \text{ and }e\in
C\right\}  \right\} \\
&  =\left\{  \underbrace{\left(  E\setminus e\right)  \setminus\left(
E\setminus C\right)  }_{\substack{=C\setminus e\\\text{(since }e\in C\text{)}%
}}\ \mid\ C\in\mathcal{B}\left(  M\right)  \text{ and }e\in C\right\} \\
&  =\left\{  C\setminus e\ \mid\ C\in\mathcal{B}\left(  M\right)  \text{ and
}e\in C\right\} \\
&  =\left\{  B\setminus e\ \mid\ B\in\mathcal{B}\left(  M\right)  \text{ and
}e\in B\right\}
\end{align*}
(here, we renamed the index $C$ as $B$). This proves Proposition
\ref{prop.delcon.con-e-bases}.
\end{proof}

\begin{proposition}
\label{prop.delcon.del=con}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. Let $e\in E$.

\textbf{(a)} If $e$ is a loop of $M$, then $M/e=M\setminus e$.

\textbf{(b)} If $e$ is a coloop of $M$, then $M/e=M\setminus e$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.delcon.del=con}.]Both matroids $M/\left\{
e\right\}  $ and $M\setminus\left\{  e\right\}  $ have the ground set
$E\setminus\left\{  e\right\}  $.

\textbf{(a)} Assume that $e$ is a loop of $M$. Proposition
\ref{prop.loops.equiv} \textbf{(a)} therefore shows that $r_{M}\left(
e\right)  =0$.

Let $S\in\mathcal{P}\left(  E\setminus\left\{  e\right\}  \right)  $.
Proposition \ref{prop.delcon.rank} \textbf{(b)} (applied to $Z=\left\{
e\right\}  $) yields%
\begin{align*}
r_{M/\left\{  e\right\}  }\left(  S\right)   &  =r_{M}\left(
\underbrace{S\cup\left\{  e\right\}  }_{=S\cup e}\right)  -\underbrace{r_{M}%
\left(  \left\{  e\right\}  \right)  }_{=r_{M}\left(  e\right)  =0}\\
&  =r_{M}\left(  S\cup e\right)  =r_{M}\left(  S\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition \ref{prop.loops.basics}
\textbf{(a)}}\right)  .
\end{align*}
But Proposition \ref{prop.delcon.rank} \textbf{(a)} (applied to $Z=\left\{
e\right\}  $) shows that $r_{M\setminus\left\{  e\right\}  }\left(  S\right)
=r_{M}\left(  S\right)  $. Comparing this with $r_{M/\left\{  e\right\}
}\left(  S\right)  =r_{M}\left(  S\right)  $, we obtain $r_{M/\left\{
e\right\}  }\left(  S\right)  =r_{M\setminus\left\{  e\right\}  }\left(
S\right)  $.

Now, let us forget that we fixed $S$. We thus have shown that $r_{M/\left\{
e\right\}  }\left(  S\right)  =r_{M\setminus\left\{  e\right\}  }\left(
S\right)  $ for every $S\in\mathcal{P}\left(  E\setminus\left\{  e\right\}
\right)  $. In other words, $r_{M/\left\{  e\right\}  }=r_{M\setminus\left\{
e\right\}  }$. Hence, Corollary \ref{cor.M-from-rank} (applied to $M/\left\{
e\right\}  $, $M\setminus\left\{  e\right\}  $ and $E\setminus\left\{
e\right\}  $ instead of $M$, $M^{\prime}$ and $E$) shows that $M/\left\{
e\right\}  =M\setminus\left\{  e\right\}  $. Thus, $M/e=M/\left\{  e\right\}
=M\setminus\left\{  e\right\}  =M\setminus e$. This proves Proposition
\ref{prop.delcon.del=con} \textbf{(a)}.

\textbf{(b)} Assume that $e$ is a coloop of $M$. In other words, $e$ is a
coloop of $\left(  M^{\ast}\right)  ^{\ast}$ (since $\left(  M^{\ast}\right)
^{\ast}=M$).

Write the matroid $M^{\ast}$ in the form $\left(  E,\mathcal{K}\right)  $.
Proposition \ref{prop.dual-loop} (applied to $M^{\ast}$ and $\mathcal{K}$
instead of $M$ and $\mathcal{I}$) shows that $e$ is a loop of $M^{\ast}$ if
and only if $e$ is a coloop of $\left(  M^{\ast}\right)  ^{\ast}$. Hence, $e$
is a loop of $M^{\ast}$ (since $e$ is a coloop of $\left(  M^{\ast}\right)
^{\ast}$). Hence, Proposition \ref{prop.delcon.del=con} \textbf{(a)} (applied
to $M^{\ast}$ and $\mathcal{K}$ instead of $M$ and $\mathcal{I}$) shows that
$M^{\ast}/e=M^{\ast}\setminus e$.

On the other hand,%
\begin{align*}
M^{\ast}/e  &  =M^{\ast}/\left\{  e\right\}  =\left(  \left(  M^{\ast}\right)
^{\ast}\setminus\left\{  e\right\}  \right)  ^{\ast}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }M^{\ast}/\left\{
e\right\}  \right) \\
&  =\left(  \underbrace{\left(  M^{\ast}\right)  ^{\ast}}_{=M}\setminus
e\right)  ^{\ast}=\left(  M\setminus e\right)  ^{\ast}.
\end{align*}


Now,%
\begin{align*}
M/e  &  =M/\left\{  e\right\}  =\left(  \underbrace{M^{\ast}\setminus\left\{
e\right\}  }_{=M^{\ast}\setminus e=M^{\ast}/e}\right)  ^{\ast}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }M/\left\{  e\right\}
\right) \\
&  =\left(  \underbrace{M^{\ast}/e}_{=\left(  M\setminus e\right)  ^{\ast}%
}\right)  ^{\ast}=\left(  \left(  M\setminus e\right)  ^{\ast}\right)  ^{\ast
}=M\setminus e.
\end{align*}
This proves Proposition \ref{prop.delcon.del=con} \textbf{(b)}.
\end{proof}

\section{The Tutte polynomial}

Let us recall the definition of the Tutte polynomial of a matroid (according
to \cite[Definition 4.1]{Martin15}):

\begin{definition}
\label{def.tutte}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. The
\textit{Tutte polynomial} of this matroid $M$ is defined to be the polynomial%
\[
\sum_{A\subseteq E}\left(  x-1\right)  ^{r_{M}\left(  E\right)  -r_{M}\left(
A\right)  }\left(  y-1\right)  ^{\left\vert A\right\vert -r_{M}\left(
A\right)  }\in\mathbb{Z}\left[  x,y\right]  .
\]
This polynomial is denoted by $T_{M}=T_{M}\left(  x,y\right)  $.
\end{definition}

This polynomial has many properties; in particular, it encodes a lot of
information about $M$. The most relevant property is the following
proposition, which gives a recursive way to compute it (starting with
$T_{\left(  \varnothing,\varnothing\right)  }=1$) without ever having to
subtract $1$:

\begin{proposition}
\label{prop.tutte.rec}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid. Let
$e\in E$.

\textbf{(a)} If $e$ is a loop, then $T_{M}=yT_{M\setminus e}$.

\textbf{(b)} If $e$ is a coloop, then $T_{M}=xT_{M/e}$.

\textbf{(c)} If $e$ is neither a loop nor a coloop, then $T_{M}=T_{M\setminus
e}+T_{M/e}$.
\end{proposition}

As a corollary, we obtain the following:

\begin{corollary}
\label{cor.tutte.positive}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid.
Then, $T_{M}\in\mathbb{N}\left[  x,y\right]  $.
\end{corollary}

Here, $\mathbb{N}\left[  x,y\right]  $ denotes the set of all polynomials
$P\in\mathbb{Z}\left[  x,y\right]  $ whose all coefficients are nonnegative integers.

Proposition \ref{prop.tutte.rec} is well-known (e.g., it is \cite[Theorem
4.5]{Martin15}); we shall not prove it right now, but it will be a consequence
of some results further below.

\section{The filtered Tutte polynomial}

Our goal in this note is to define a generalization of the Tutte polynomial
$T_{M}$ for matroids $M$ equipped with a \textit{filtration}, i.e., a weakly
increasing chain $\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq
E_{m}=E$ of subsets of $E$. This generalization will be called the
\textit{filtered Tutte polynomial}. Let us first define filtered matroids:

\begin{definition}
\label{def.filtmat}A \textit{filtered matroid} means a pair $\left(
M,\mathbf{E}\right)  $, where $M=\left(  E,\mathcal{I}\right)  $ is a matroid,
and where $\mathbf{E}$ is a finite list $\left(  E_{0},E_{1},\ldots
,E_{m}\right)  $ of subsets of $E$ such that%
\[
\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}=E.
\]

\end{definition}

\begin{definition}
Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a filtered matroid, with
$M=\left(  E,\mathcal{I}\right)  $. Let $e\in E$. Then, $\mathbf{E}\setminus
e$ shall denote the list $\left(  E_{0}\setminus e,E_{1}\setminus
e,\ldots,E_{m}\setminus e\right)  $, where the list $\mathbf{E}$ is written as
$\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. We let $\mathbf{M}\setminus e$
and $\mathbf{M}/e$ denote the filtered matroids $\left(  M\setminus
e,\mathbf{E}\setminus e\right)  $ and $\left(  M/e,\mathbf{E}\setminus
e\right)  $.
\end{definition}

\begin{definition}
\label{def.filtutte}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. The
\textit{filtered Tutte polynomial} of this filtered matroid $\mathbf{M}$ is
defined to be the polynomial%
\begin{align*}
&  \sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)
^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
}\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M}\left(
A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right) \\
&  \in\mathbb{Z}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots
,y_{m}\right]  .
\end{align*}
This polynomial is well-defined\footnotemark, and is denoted by $T_{\mathbf{M}%
}$.
\end{definition}

\footnotetext{\textit{Proof.} We only need to show the following two
statements:
\par
\begin{quote}
\textit{Statement 1:} We have $r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(
A\cup E_{i-1}\right)  \in\mathbb{N}$ for every $i\in\left\{  1,2,\ldots
,m\right\}  $.
\par
\textit{Statement 2:} We have $n_{M}\left(  A\setminus E_{i-1}\right)
-n_{M}\left(  A\setminus E_{i}\right)  \in\mathbb{N}$ for every $i\in\left\{
1,2,\ldots,m\right\}  $.
\end{quote}
\par
\textit{Proof of Statement 1:} Let $i\in\left\{  1,2,\ldots,m\right\}  $. We
have $\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}=E$ (since
$\left(  M,\mathbf{E}\right)  $ is a filtered matroid) and thus $E_{i-1}%
\subseteq E_{i}$. Hence, $A\cup\underbrace{E_{i-1}}_{\subseteq E_{i}}\subseteq
A\cup E_{i}$. Therefore, (\ref{eq.def.rank.incr}) (applied to $S=A\cup
E_{i-1}$ and $T=A\cup E_{i}$) shows that $r_{M}\left(  A\cup E_{i-1}\right)
\leq r_{M}\left(  A\cup E_{i}\right)  $. In other words, $r_{M}\left(  A\cup
E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  \in\mathbb{N}$. This proves
Statement 1.
\par
\textit{Proof of Statement 2:} Let $i\in\left\{  1,2,\ldots,m\right\}  $. We
have $\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}=E$ (since
$\left(  M,\mathbf{E}\right)  $ is a filtered matroid) and thus $E_{i-1}%
\subseteq E_{i}$. In other words, $E_{i}\supseteq E_{i-1}$. Hence,
$A\setminus\underbrace{E_{i}}_{\supseteq E_{i-1}}\subseteq A\setminus E_{i-1}%
$. Therefore, (\ref{eq.prop.nullity.monotone.b.eq}) (applied to $S=A\setminus
E_{i}$ and $T=A\setminus E_{i-1}$) shows that $n_{M}\left(  A\setminus
E_{i}\right)  \leq n_{M}\left(  A\setminus E_{i-1}\right)  $. In other words,
$n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  \in\mathbb{N}$. This proves Statement 2.} Filtered Tutte
polynomials have the following properties:

\begin{proposition}
\label{prop.filtutte.proj}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. Then, in the
polynomial ring $\mathbb{Z}\left[  x,y\right]  $, we have%
\[
T_{\mathbf{M}}\left(  \underbrace{x,x,\ldots,x}_{m\text{ times}}%
,\underbrace{y,y,\ldots,y}_{m\text{ times}}\right)  =T_{M}\left(  x,y\right)
.
\]

\end{proposition}

\begin{proposition}
\label{prop.filtutte.m=1}Let $M=\left(  E,\mathcal{I}\right)  $ be a matroid,
and let $\mathbf{E}$ be the list $\left(  \varnothing,E\right)  $. Then,
$\left(  M,\mathbf{E}\right)  $ is a filtered matroid, and satisfies%
\[
T_{\left(  M,\mathbf{E}\right)  }=T_{M}\left(  x_{1},y_{1}\right)  .
\]

\end{proposition}

\begin{proposition}
\label{prop.filtutte.m=0}We have $T_{\left(  \left(  \varnothing
,\varnothing\right)  ,\left(  \varnothing\right)  \right)  }=1$.
\end{proposition}

\begin{proposition}
\label{prop.filtutte.m-1}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. Assume that
$E_{m-1}=E_{m}$. Let $\mathbf{E}^{\prime}$ be the list $\left(  E_{0}%
,E_{1},\ldots,E_{m-1}\right)  $. Then, $\left(  M,\mathbf{E}^{\prime}\right)
$ is a filtered matroid, and satisfies%
\[
T_{\left(  M,\mathbf{E}\right)  }=T_{\left(  M,\mathbf{E}^{\prime}\right)  }.
\]
(Here, we regard $\mathbb{Z}\left[  x_{1},x_{2},\ldots,x_{m-1},y_{1}%
,y_{2},\ldots,y_{m-1}\right]  $ as a subring of $\mathbb{Z}\left[  x_{1}%
,x_{2},\ldots,x_{m},y_{1},y_{2},\ldots,y_{m}\right]  $ in the obvious way.)
\end{proposition}

\begin{proposition}
\label{prop.filtutte.rec}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. Let $e\in E$.

\textbf{(a)} If $e$ is a loop, then $T_{\mathbf{M}}=y_{k}T_{\mathbf{M}%
\setminus e}$, where $k\in\left\{  1,2,\ldots,m\right\}  $ is such that $e\in
E_{k}\setminus E_{k-1}$.

\textbf{(b)} If $e$ is a coloop, then $T_{\mathbf{M}}=x_{k}T_{\mathbf{M}/e}$,
where $k\in\left\{  1,2,\ldots,m\right\}  $ is such that $e\in E_{k}\setminus
E_{k-1}$.

\textbf{(c)} If $e$ belongs to $E_{m}\setminus E_{m-1}$ and is neither a loop
nor a coloop, then $T_{\mathbf{M}}=T_{\mathbf{M}\setminus e}+T_{\mathbf{M}/e}$.
\end{proposition}

We do not know whether Proposition \ref{prop.filtutte.rec} can be extended to
the case when $e$ does not belong to $E_{m}\setminus E_{m-1}$.

\begin{proposition}
\label{prop.filtutte.pos}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid. Write the list $\mathbf{E}$ as $\left(  E_{0},E_{1}%
,\ldots,E_{m}\right)  $. Then, $T_{\mathbf{M}}\in\mathbb{N}\left[  x_{1}%
,x_{2},\ldots,x_{m},y_{1},y_{2},\ldots,y_{m}\right]  $.
\end{proposition}

Here, $\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots
,y_{m}\right]  $ denotes the set of all polynomials $P\in\mathbb{Z}\left[
x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots,y_{m}\right]  $ whose all
coefficients are nonnegative integers.

\begin{proposition}
\label{prop.filtutte.dual}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $.

Then, $\left(  M^{\ast},\mathbf{E}\right)  $ is a filtered matroid as well,
and satisfies%
\[
T_{\left(  M^{\ast},\mathbf{E}\right)  }=T_{\mathbf{M}}\left(  y_{1}%
,y_{2},\ldots,y_{m},x_{1},x_{2},\ldots,x_{m}\right)  .
\]

\end{proposition}

We shall now prove the properties listed above.

\begin{proof}
[Proof of Proposition \ref{prop.filtutte.proj}.]By the telescope principle, we
have%
\begin{align}
&  \sum_{i=1}^{m}\left(  r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  \right) \nonumber\\
&  =r_{M}\left(  A\cup\underbrace{E_{m}}_{=E}\right)  -r_{M}\left(
A\cup\underbrace{E_{0}}_{=\varnothing}\right)  =r_{M}\left(  \underbrace{A\cup
E}_{\substack{=E\\\text{(since }A\subseteq E\text{)}}}\right)  -r_{M}\left(
\underbrace{A\cup\varnothing}_{=A}\right) \nonumber\\
&  =r_{M}\left(  E\right)  -r_{M}\left(  A\right)  .
\label{pf.prop.filtutte.proj.1}%
\end{align}
By the telescope principle, we have%
\begin{align}
&  \sum_{i=1}^{m}\left(  n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(
A\setminus E_{i}\right)  \right) \nonumber\\
&  =n_{M}\left(  A\setminus\underbrace{E_{0}}_{=\varnothing}\right)
-n_{M}\left(  A\setminus\underbrace{E_{m}}_{=E}\right)  =n_{M}\left(
\underbrace{A\setminus\varnothing}_{=A}\right)  -n_{M}\left(
\underbrace{A\setminus E}_{\substack{=\varnothing\\\text{(since }A\subseteq
E\text{)}}}\right) \nonumber\\
&  =n_{M}\left(  A\right)  -\underbrace{n_{M}\left(  \varnothing\right)
}_{=0}=n_{M}\left(  A\right)  =\left\vert A\right\vert -r_{M}\left(  A\right)
\label{pf.prop.filtutte.proj.2}%
\end{align}
(by the definition of $n_{M}\left(  A\right)  $).

The definition of $T_{\mathbf{M}}$ yields%
\begin{align*}
&  T_{\mathbf{M}}\left(  \underbrace{x,x,\ldots,x}_{m\text{ times}%
},\underbrace{y,y,\ldots,y}_{m\text{ times}}\right) \\
&  =\sum_{A\subseteq E}\underbrace{\left(  \prod_{i=1}^{m}\left(  x-1\right)
^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
}\right)  }_{=\left(  x-1\right)  ^{\sum_{i=1}^{m}\left(  r_{M}\left(  A\cup
E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  \right)  }}%
\underbrace{\left(  \prod_{i=1}^{m}\left(  y-1\right)  ^{n_{M}\left(
A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right)
}_{=\left(  y-1\right)  ^{\sum_{i=1}^{m}\left(  n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  \right)  }}\\
&  =\sum_{A\subseteq E}\left(  x-1\right)  ^{\sum_{i=1}^{m}\left(
r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  \right)
}\left(  y-1\right)  ^{\sum_{i=1}^{m}\left(  n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  \right)  }\\
&  =\sum_{A\subseteq E}\left(  x-1\right)  ^{r_{M}\left(  E\right)
-r_{M}\left(  A\right)  }\left(  y-1\right)  ^{\left\vert A\right\vert
-r_{M}\left(  A\right)  }\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.prop.filtutte.proj.1}) and (\ref{pf.prop.filtutte.proj.2})}\right) \\
&  =T_{M}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }T_{M}\right)
\\
&  =T_{M}\left(  x,y\right)  .
\end{align*}
This proves Proposition \ref{prop.filtutte.proj}.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.filtutte.m=1}.]We have $\varnothing
=\varnothing\subseteq E=E$. Thus, $\left(  M,\mathbf{E}\right)  $ is a
filtered matroid. It remains to show that $T_{\left(  M,\mathbf{E}\right)
}=T_{M}\left(  x_{1},y_{1}\right)  $.

Proposition \ref{prop.filtutte.proj} (applied to $m=1$, $\left(  E_{0}%
,E_{1},\ldots,E_{m}\right)  =\left(  \varnothing,E\right)  $ and
$\mathbf{M}=\left(  M,\mathbf{E}\right)  $) yields $T_{\left(  M,\mathbf{E}%
\right)  }\left(  \underbrace{x,x,\ldots,x}_{1\text{ times}}%
,\underbrace{y,y,\ldots,y}_{1\text{ times}}\right)  =T_{M}\left(  x,y\right)
=T_{M}$. Thus,%
\[
T_{M}=T_{\left(  M,\mathbf{E}\right)  }\left(  \underbrace{x,x,\ldots
,x}_{1\text{ times}},\underbrace{y,y,\ldots,y}_{1\text{ times}}\right)
=T_{\left(  M,\mathbf{E}\right)  }\left(  x,y\right)  .
\]
Substituting $x_{1}$ and $y_{1}$ for $x$ and $y$ on both sides of this
equality, we obtain $T_{M}\left(  x_{1},y_{1}\right)  =\left(  T_{\left(
M,\mathbf{E}\right)  }\left(  x,y\right)  \right)  \left(  x_{1},y_{1}\right)
=T_{\left(  M,\mathbf{E}\right)  }$. In other words, $T_{\left(
M,\mathbf{E}\right)  }=T_{M}\left(  x_{1},y_{1}\right)  $. This completes the
proof of Proposition \ref{prop.filtutte.m=1}.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.filtutte.m=0}.]Proposition
\ref{prop.filtutte.m=0} follows straightforwardly from the definition.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.filtutte.m-1}.]Since $\left(  M,\mathbf{E}%
\right)  $ is a filtered matroid, we have $\varnothing=E_{0}\subseteq
E_{1}\subseteq\cdots\subseteq E_{m}=E$. Combined with $E_{m-1}=E_{m}$, this
yields $\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m-1}=E$.
Thus, $\left(  M,\mathbf{E}^{\prime}\right)  $ is a filtered matroid. It
remains to prove that $T_{\left(  M,\mathbf{E}\right)  }=T_{\left(
M,\mathbf{E}^{\prime}\right)  }$.

The definition of $T_{\left(  M,\mathbf{E}^{\prime}\right)  }$ yields%
\[
T_{\left(  M,\mathbf{E}^{\prime}\right)  }=\sum_{A\subseteq E}\left(
\prod_{i=1}^{m-1}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)
-r_{M}\left(  A\cup E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m-1}\left(
y_{i}-1\right)  ^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(
A\setminus E_{i}\right)  }\right)  .
\]
But
\begin{align*}
&  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)
-r_{M}\left(  A\cup E_{i-1}\right)  }\\
&  =\left(  \prod_{i=1}^{m-1}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup
E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  }\right)
\underbrace{\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{m}\right)
-r_{M}\left(  A\cup E_{m-1}\right)  }}_{\substack{=1\\\text{(since }%
E_{m-1}=E_{m}\text{, so that}\\r_{M}\left(  A\cup E_{m-1}\right)
=r_{M}\left(  A\cup E_{m}\right)  \text{, so that}\\r_{M}\left(  A\cup
E_{m}\right)  -r_{M}\left(  A\cup E_{m-1}\right)  =0\text{)}}}\\
&  =\prod_{i=1}^{m-1}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup
E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  }%
\end{align*}
and%
\begin{align*}
&  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\\
&  =\left(  \prod_{i=1}^{m-1}\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right)
\underbrace{\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus E_{m-1}\right)
-n_{M}\left(  A\setminus E_{m}\right)  }}_{\substack{=1\\\text{(since }%
E_{m-1}=E_{m}\text{, so that}\\n_{M}\left(  A\setminus E_{m-1}\right)
=n_{M}\left(  A\setminus E_{m}\right)  \text{, so that}\\n_{M}\left(
A\setminus E_{m-1}\right)  -n_{M}\left(  A\setminus E_{m}\right)  =0\text{)}%
}}\\
&  =\prod_{i=1}^{m-1}\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }.
\end{align*}
Now, the definition of $T_{\left(  M,\mathbf{E}\right)  }$ yields%
\begin{align*}
T_{\left(  M,\mathbf{E}\right)  }  &  =\sum_{A\subseteq E}\underbrace{\left(
\prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)
-r_{M}\left(  A\cup E_{i-1}\right)  }\right)  }_{=\prod_{i=1}^{m-1}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }}\underbrace{\left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  }_{=\prod_{i=1}^{m-1}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }}\\
&  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m-1}\left(  x_{i}-1\right)
^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
}\right)  \left(  \prod_{i=1}^{m-1}\left(  y_{i}-1\right)  ^{n_{M}\left(
A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right) \\
&  =T_{\left(  M,\mathbf{E}^{\prime}\right)  }.
\end{align*}
This completes the proof of Proposition \ref{prop.filtutte.m-1}.
\end{proof}

We shall now prepare for the proof of Proposition \ref{prop.filtutte.rec}.

First, we introduce the \textit{Iverson bracket notation}: If $\mathcal{S}$ is
any logical statement, then $\left[  \mathcal{S}\right]  $ shall mean the
integer $%
\begin{cases}
1, & \text{if }\mathcal{S}\text{ is true;}\\
0, & \text{if }\mathcal{S}\text{ is false}%
\end{cases}
$.

Next, we shall show some lemmas:

\begin{lemma}
\label{lem.delcon.rank.lem1}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. Let $e\in E$. Let $A\in\mathcal{P}\left(  E\right)  $ be such that
$e\notin A$. Let $K\in\mathcal{P}\left(  E\right)  $. Then,%
\[
r_{M}\left(  \left(  A\cup e\right)  \cup K\right)  =r_{M/e}\left(
A\cup\left(  K\setminus e\right)  \right)  +r_{M}\left(  e\right)  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.delcon.rank.lem1}.]We have $e\notin A$, thus
$A\subseteq E\setminus\left\{  e\right\}  $.

Let $S=A\cup\left(  K\setminus e\right)  $. Then, $S=\underbrace{A}_{\subseteq
E\setminus\left\{  e\right\}  =E\setminus e}\cup\left(  \underbrace{K}%
_{\subseteq E}\setminus e\right)  \subseteq\left(  E\setminus e\right)
\cup\left(  E\setminus e\right)  =E\setminus e$. In other words,
$S\in\mathcal{P}\left(  E\setminus\left\{  e\right\}  \right)  $. Thus,
Proposition \ref{prop.delcon.rank} \textbf{(b)} (applied to $Z=\left\{
e\right\}  $) shows that $r_{M/\left\{  e\right\}  }\left(  S\right)
=r_{M}\left(  S\cup\left\{  e\right\}  \right)  -r_{M}\left(  \left\{
e\right\}  \right)  $. Since $M/\left\{  e\right\}  =M/e$, $S\cup\left\{
e\right\}  =S\cup e$ and $r_{M}\left(  \left\{  e\right\}  \right)
=r_{M}\left(  e\right)  $, this rewrites as $r_{M/e}\left(  S\right)
=r_{M}\left(  S\cup e\right)  -r_{M}\left(  e\right)  $.

But
\[
\underbrace{S}_{=A\cup\left(  K\setminus e\right)  }\cup e=A\cup
\underbrace{\left(  K\setminus e\right)  \cup e}_{=K\cup e}=A\cup K\cup e.
\]
Now,%
\begin{align*}
r_{M/e}\left(  \underbrace{A\cup\left(  K\setminus e\right)  }_{=S}\right)
&  =r_{M/e}\left(  S\right)  =r_{M}\left(  \underbrace{S\cup e}_{=A\cup K\cup
e=\left(  A\cup e\right)  \cup K}\right)  -r_{M}\left(  e\right) \\
&  =r_{M}\left(  \left(  A\cup e\right)  \cup K\right)  -r_{M}\left(
e\right)  .
\end{align*}
In other words, $r_{M}\left(  \left(  A\cup e\right)  \setminus K\right)
=r_{M/e}\left(  A\cup\left(  K\setminus e\right)  \right)  +r_{M}\left(
e\right)  $. This proves Lemma \ref{lem.delcon.rank.lem1}.
\end{proof}

\begin{lemma}
\label{lem.delcon.rank.lem2}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. Let $e\in E$. Let $A\in\mathcal{P}\left(  E\right)  $ be such that
$e\notin A$. Let $K\in\mathcal{P}\left(  E\right)  $.

\textbf{(a)} If $e\in K$, then%
\begin{align*}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus K\right) \\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  -r_{M}\left(
A\setminus K\right)  -r_{M}\left(  e\right)  .
\end{align*}


\textbf{(b)} If $e\notin K$, then%
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  +1-r_{M}\left(  e\right)  .
\]


\textbf{(c)} If $e$ is a loop, then%
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  +\left[  e\notin K\right]  .
\]


\textbf{(d)} If $e$ is a coloop, then%
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  .
\]


\textbf{(e)} If $K=E$, then%
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.delcon.rank.lem2}.]Let $S=A\setminus\left(
K\setminus e\right)  $. Then, $S\subseteq A\subseteq E\setminus\left\{
e\right\}  $. In other words, $S\in\mathcal{P}\left(  E\setminus\left\{
e\right\}  \right)  $. Thus, Proposition \ref{prop.delcon.rank} \textbf{(b)}
(applied to $Z=\left\{  e\right\}  $) shows that $r_{M/\left\{  e\right\}
}\left(  S\right)  =r_{M}\left(  S\cup\left\{  e\right\}  \right)
-r_{M}\left(  \left\{  e\right\}  \right)  $. Since $M/\left\{  e\right\}
=M/e$, $S\cup\left\{  e\right\}  =S\cup e$ and $r_{M}\left(  \left\{
e\right\}  \right)  =r_{M}\left(  e\right)  $, this rewrites as $r_{M/e}%
\left(  S\right)  =r_{M}\left(  S\cup e\right)  -r_{M}\left(  e\right)  $.

But $S=A\setminus\left(  K\setminus e\right)  \subseteq\left(  A\setminus
K\right)  \cup e$. Hence,
\[
\underbrace{S}_{\subseteq\left(  A\setminus K\right)  \cup e}\cup
e\subseteq\left(  A\setminus K\right)  \cup e\cup e=\left(  A\setminus
K\right)  \cup e.
\]
Combining this with $\underbrace{\left(  A\setminus K\right)  }_{\subseteq
A\setminus\left(  K\setminus e\right)  =S}\cup e\subseteq S\cup e$, this
yields $S\cup e=\left(  A\setminus K\right)  \cup e$. Now,
\[
r_{M/e}\left(  \underbrace{A\setminus\left(  K\setminus e\right)  }%
_{=S}\right)  =r_{M}\left(  S\right)  =r_{M}\left(  \underbrace{S\cup
e}_{=\left(  A\setminus K\right)  \cup e}\right)  -r_{M}\left(  e\right)
=r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  -r_{M}\left(
e\right)  .
\]


On the other hand,%
\begin{align}
&  \underbrace{n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)
}_{\substack{=\left\vert \left(  A\cup e\right)  \setminus K\right\vert
-r_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  \\\text{(by the
definition of }n_{M}\text{)}}}-\underbrace{n_{M/e}\left(  A\setminus\left(
K\setminus e\right)  \right)  }_{\substack{=\left\vert A\setminus\left(
K\setminus e\right)  \right\vert -r_{M/e}\left(  A\setminus\left(  K\setminus
e\right)  \right)  \\\text{(by the definition of }n_{M/e}\text{)}}}\nonumber\\
&  =\left(  \left\vert \left(  A\cup e\right)  \setminus K\right\vert
-r_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  \right)  -\left(
\left\vert A\setminus\left(  K\setminus e\right)  \right\vert
-\underbrace{r_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
}_{=r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  -r_{M}\left(
e\right)  }\right) \nonumber\\
&  =\left(  \left\vert \left(  A\cup e\right)  \setminus K\right\vert
-r_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  \right)  -\left(
\left\vert A\setminus\left(  K\setminus e\right)  \right\vert -\left(
r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  -r_{M}\left(
e\right)  \right)  \right) \nonumber\\
&  =\left\vert \left(  A\cup e\right)  \setminus K\right\vert -r_{M}\left(
\left(  A\cup e\right)  \setminus K\right)  -\left\vert A\setminus\left(
K\setminus e\right)  \right\vert +r_{M}\left(  \left(  A\setminus K\right)
\cup e\right)  -r_{M}\left(  e\right)  . \label{pf.lem.delcon.rank.lem2.gen1}%
\end{align}


\textbf{(a)} Assume that $e\in K$. Combined with $e\notin A$, this readily
yields $\left(  A\cup e\right)  \setminus K=A\setminus\left(  K\setminus
e\right)  $. Also, $\left(  A\cup e\right)  \setminus K=A\setminus K$ (since
$e\in K$). Hence, (\ref{pf.lem.delcon.rank.lem2.gen1}) becomes%
\begin{align*}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  -n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right) \\
&  =\left\vert \underbrace{\left(  A\cup e\right)  \setminus K}_{=A\setminus
\left(  K\setminus e\right)  }\right\vert -r_{M}\left(  \underbrace{\left(
A\cup e\right)  \setminus K}_{=A\setminus K}\right)  -\left\vert
A\setminus\left(  K\setminus e\right)  \right\vert +r_{M}\left(  \left(
A\setminus K\right)  \cup e\right)  -r_{M}\left(  e\right) \\
&  =\left\vert A\setminus\left(  K\setminus e\right)  \right\vert
-r_{M}\left(  A\setminus K\right)  -\left\vert A\setminus\left(  K\setminus
e\right)  \right\vert +r_{M}\left(  \left(  A\setminus K\right)  \cup
e\right)  -r_{M}\left(  e\right) \\
&  =r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  -r_{M}\left(
A\setminus K\right)  -r_{M}\left(  e\right)  .
\end{align*}
In other words,%
\begin{align*}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus K\right) \\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  -r_{M}\left(
A\setminus K\right)  -r_{M}\left(  e\right)  .
\end{align*}
This proves Lemma \ref{lem.delcon.rank.lem2} \textbf{(a)}.

\textbf{(b)} Assume that $e\notin K$. Combined with $e\notin A$, this readily
yields $\left(  A\cup e\right)  \setminus K=\left(  A\setminus\left(
K\setminus e\right)  \right)  \cup e$. Thus, $\left\vert \left(  A\cup
e\right)  \setminus K\right\vert =\left\vert \left(  A\setminus\left(
K\setminus e\right)  \right)  \cup e\right\vert =\left\vert A\setminus\left(
K\setminus e\right)  \right\vert +1$ (since $e\notin A\setminus\left(
K\setminus e\right)  $ (since $e\notin A$)). Also, $\left(  A\cup e\right)
\setminus K=\left(  A\setminus K\right)  \cup e$ (since $e\notin K$). Hence,
(\ref{pf.lem.delcon.rank.lem2.gen1}) becomes%
\begin{align*}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  -n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right) \\
&  =\underbrace{\left\vert \left(  A\cup e\right)  \setminus K\right\vert
}_{=\left\vert A\setminus\left(  K\setminus e\right)  \right\vert +1}%
-r_{M}\left(  \underbrace{\left(  A\cup e\right)  \setminus K}_{=\left(
A\setminus K\right)  \cup e}\right)  -\left\vert A\setminus\left(  K\setminus
e\right)  \right\vert +r_{M}\left(  \left(  A\setminus K\right)  \cup
e\right)  -r_{M}\left(  e\right) \\
&  =\left\vert A\setminus\left(  K\setminus e\right)  \right\vert
+1-r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  -\left\vert
A\setminus\left(  K\setminus e\right)  \right\vert +r_{M}\left(  \left(
A\setminus K\right)  \cup e\right)  -r_{M}\left(  e\right) \\
&  =1-r_{M}\left(  e\right)  .
\end{align*}
In other words,%
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  +1-r_{M}\left(  e\right)  .
\]
This proves Lemma \ref{lem.delcon.rank.lem2} \textbf{(b)}.

\textbf{(c)} Assume that $e$ is a loop. We need to show that
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  +\left[  e\notin K\right]  .
\]


We know that $e$ is a loop. Thus, $r_{M}\left(  e\right)  =0$ (by Proposition
\ref{prop.loops.equiv} \textbf{(a)}). Proposition \ref{prop.loops.basics}
\textbf{(a)} (applied to $S=A\setminus K$) yields $r_{M}\left(  \left(
A\setminus K\right)  \cup e\right)  =r_{M}\left(  A\setminus K\right)  $.

We are in one of the following two cases:

\textit{Case 1:} We have $e\in K$.

\textit{Case 2:} We have $e\notin K$.

Let us first consider Case 1. In this case, we have $e\in K$. Thus, Lemma
\ref{lem.delcon.rank.lem2} \textbf{(a)} yields
\begin{align*}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus K\right) \\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+\underbrace{r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)
}_{=r_{M}\left(  A\setminus K\right)  }-r_{M}\left(  A\setminus K\right)
-\underbrace{r_{M}\left(  e\right)  }_{=0}\\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+r_{M}\left(  A\setminus K\right)  -r_{M}\left(  A\setminus K\right) \\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  .
\end{align*}
Compared with
\[
n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+\underbrace{\left[  e\notin K\right]  }_{\substack{=0\\\text{(since }e\in
K\text{)}}}=n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  ,
\]
this yields $n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)
=n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  +\left[
e\notin K\right]  $. Thus, Lemma \ref{lem.delcon.rank.lem2} \textbf{(c)} is
proven in Case 1.

Let us now consider Case 2. In this case, we have $e\notin K$. Hence, Lemma
\ref{lem.delcon.rank.lem2} \textbf{(b)} yields
\begin{align*}
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)   &  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  +1-\underbrace{r_{M}\left(
e\right)  }_{=0}\\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  +1.
\end{align*}
Compared with%
\[
n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+\underbrace{\left[  e\notin K\right]  }_{\substack{=1\\\text{(since }e\notin
K\text{)}}}=n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+1,
\]
this yields $n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)
=n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  +\left[
e\notin K\right]  $. Thus, Lemma \ref{lem.delcon.rank.lem2} \textbf{(c)} is
proven in Case 2.

Hence, Lemma \ref{lem.delcon.rank.lem2} \textbf{(c)} is proven in each of the
two Cases 1 and 2. Thus, Lemma \ref{lem.delcon.rank.lem2} \textbf{(c)} always holds.

\textbf{(d)} Assume that $e$ is a coloop. We need to show that $n_{M}\left(
\left(  A\cup e\right)  \setminus K\right)  =n_{M/e}\left(  A\setminus\left(
K\setminus e\right)  \right)  +1$.

We know that $e$ is a coloop. Thus, Proposition \ref{prop.loops.basics}
\textbf{(b)} (applied to $S=\varnothing$) yields $r_{M}\left(  \varnothing\cup
e\right)  =\underbrace{r_{M}\left(  \varnothing\right)  }_{=0}+1=1$. Since
$r_{M}\left(  \underbrace{\varnothing\cup e}_{=\left\{  e\right\}  }\right)
=r_{M}\left(  \left\{  e\right\}  \right)  =r_{M}\left(  e\right)  $, this
rewrites as $r_{M}\left(  e\right)  =1$. But Proposition
\ref{prop.loops.basics} \textbf{(b)} (applied to $S=A\setminus K$) yields
$r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)  =r_{M}\left(
A\setminus K\right)  +1$ (since $e\notin A\setminus K$ (since $e\notin A$)).

We are in one of the following two cases:

\textit{Case 1:} We have $e\in K$.

\textit{Case 2:} We have $e\notin K$.

Let us first consider Case 1. In this case, we have $e\in K$. Thus, Lemma
\ref{lem.delcon.rank.lem2} \textbf{(a)} yields
\begin{align*}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus K\right) \\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+\underbrace{r_{M}\left(  \left(  A\setminus K\right)  \cup e\right)
}_{=r_{M}\left(  A\setminus K\right)  +1}-r_{M}\left(  A\setminus K\right)
-\underbrace{r_{M}\left(  e\right)  }_{=1}\\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+r_{M}\left(  A\setminus K\right)  +1-r_{M}\left(  A\setminus K\right)  -1\\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  .
\end{align*}
Thus, Lemma \ref{lem.delcon.rank.lem2} \textbf{(d)} is proven in Case 1.

Let us now consider Case 2. In this case, we have $e\notin K$. Hence, Lemma
\ref{lem.delcon.rank.lem2} \textbf{(b)} yields
\begin{align*}
n_{M}\left(  \left(  A\cup e\right)  \setminus K\right)   &  =n_{M/e}\left(
A\setminus\left(  K\setminus e\right)  \right)  +1-\underbrace{r_{M}\left(
e\right)  }_{=1}\\
&  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)
+1-1=n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  .
\end{align*}
Thus, Lemma \ref{lem.delcon.rank.lem2} \textbf{(d)} is proven in Case 2.

Hence, Lemma \ref{lem.delcon.rank.lem2} \textbf{(d)} is proven in each of the
two Cases 1 and 2. Thus, Lemma \ref{lem.delcon.rank.lem2} \textbf{(d)} always holds.

\textbf{(e)} Assume that $K=E$.

From $A\cup e\subseteq E=K$, we obtain $\left(  A\cup e\right)  \setminus
K=\varnothing$, so that $n_{M}\left(  \underbrace{\left(  A\cup e\right)
\setminus K}_{=\varnothing}\right)  =n_{M}\left(  \varnothing\right)  =0$.

On the other hand, $A\subseteq E=K$. Combined with $e\notin A$, this yields
$A\subseteq K\setminus e$. Thus, $A\setminus\left(  K\setminus e\right)
=\varnothing$, so that $n_{M/e}\left(  \underbrace{A\setminus\left(
K\setminus e\right)  }_{=\varnothing}\right)  =n_{M/e}\left(  \varnothing
\right)  =0$. Compared with $n_{M}\left(  \left(  A\cup e\right)  \setminus
K\right)  =0$, this yields $n_{M}\left(  \left(  A\cup e\right)  \setminus
K\right)  =n_{M/e}\left(  A\setminus\left(  K\setminus e\right)  \right)  $.
This proves Lemma \ref{lem.delcon.rank.lem2} \textbf{(e)}.
\end{proof}

\begin{lemma}
\label{lem.delcon.rank.lem3}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. Let $e\in E$. Let $A\in\mathcal{P}\left(  E\right)  $ be such that
$e\notin A$. Let $K\in\mathcal{P}\left(  E\right)  $.

\textbf{(a)} If $e$ is a loop, then%
\[
r_{M}\left(  A\cup K\right)  =r_{M\setminus e}\left(  A\cup\left(  K\setminus
e\right)  \right)  .
\]


\textbf{(b)} If $e$ is a coloop, then%
\[
r_{M}\left(  A\cup K\right)  =r_{M\setminus e}\left(  A\cup\left(  K\setminus
e\right)  \right)  +\left[  e\in K\right]  .
\]


\textbf{(c)} If $K=E$ and if $e$ is not a coloop, then%
\[
r_{M}\left(  A\cup K\right)  =r_{M\setminus e}\left(  A\cup\left(  K\setminus
e\right)  \right)  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.delcon.rank.lem3}.]We have $e\notin A$, thus
$A\subseteq E\setminus e$. Hence, $\underbrace{A}_{\subseteq E\setminus e}%
\cup\left(  \underbrace{K}_{\subseteq E}\setminus e\right)  \subseteq\left(
E\setminus e\right)  \cup\left(  E\setminus e\right)  =E\setminus e$. In other
words, $A\cup\left(  K\setminus e\right)  \in\mathcal{P}\left(  E\setminus
e\right)  $. Hence, Proposition \ref{prop.delcon.rank} \textbf{(a)} (applied
to $Z=\left\{  e\right\}  $ and $S=A\cup\left(  K\setminus e\right)  $) shows
that $r_{M\setminus\left\{  e\right\}  }\left(  A\cup\left(  K\setminus
e\right)  \right)  =r_{M}\left(  A\cup\left(  K\setminus e\right)  \right)  $.
Since $M\setminus\left\{  e\right\}  =M\setminus e$, this rewrites as
$r_{M\setminus e}\left(  A\cup\left(  K\setminus e\right)  \right)
=r_{M}\left(  A\cup\left(  K\setminus e\right)  \right)  $.

\textbf{(a)} Assume that $e$ is a loop.

If $K\setminus e=K$, then%
\[
r_{M\setminus e}\left(  A\cup\left(  K\setminus e\right)  \right)
=r_{M}\left(  A\cup\underbrace{\left(  K\setminus e\right)  }_{=K}\right)
=r_{M}\left(  A\cup K\right)  .
\]
Hence, Lemma \ref{lem.delcon.rank.lem3} \textbf{(a)} holds in the case when
$K\setminus e=K$. Thus, for the rest of this proof, we WLOG assume that
$K\setminus e\neq K$.

If we had $e\notin K$, then we would have $K\setminus e=K$, which would
contradict $K\setminus e\neq K$. Hence, we cannot have $e\notin K$. Thus,
$e\in K$. Hence, $\left(  K\setminus e\right)  \cup e=K$.

But Proposition \ref{prop.loops.basics} \textbf{(a)} (applied to
$S=A\cup\left(  K\setminus e\right)  $) shows that $r_{M}\left(  A\cup\left(
K\setminus e\right)  \cup e\right)  =r_{M}\left(  A\cup\left(  K\setminus
e\right)  \right)  $. Hence, $r_{M}\left(  A\cup\left(  K\setminus e\right)
\right)  =r_{M}\left(  A\cup\underbrace{\left(  K\setminus e\right)  \cup
e}_{=K}\right)  =r_{M}\left(  A\cup K\right)  $. Hence,%
\[
r_{M\setminus e}\left(  A\cup\left(  K\setminus e\right)  \right)
=r_{M}\left(  A\cup\left(  K\setminus e\right)  \right)  =r_{M}\left(  A\cup
K\right)  .
\]
This proves Lemma \ref{lem.delcon.rank.lem3}.

\textbf{(b)} Assume that $e$ is a coloop.

We are in one of the following two cases:

\textit{Case 1:} We have $e\in K$.

\textit{Case 2:} We have $e\notin K$.

Let us first consider Case 1. In this case, we have $e\in K$. Thus, $\left(
K\setminus e\right)  \cup e=K$.

But $e\notin A\cup\left(  K\setminus e\right)  $ (since $e\notin A$ and
$e\notin K\setminus e$). Hence, Proposition \ref{prop.loops.basics}
\textbf{(b)} (applied to $S=A\cup\left(  K\setminus e\right)  $) shows that
$r_{M}\left(  A\cup\left(  K\setminus e\right)  \cup e\right)  =r_{M}\left(
A\cup\left(  K\setminus e\right)  \right)  +1$. Since $A\cup
\underbrace{\left(  K\setminus e\right)  \cup e}_{=K}=A\cup K$, this rewrites
as $r_{M}\left(  A\cup K\right)  =r_{M}\left(  A\cup\left(  K\setminus
e\right)  \right)  +1$. Compared with $\underbrace{r_{M\setminus e}\left(
A\cup\left(  K\setminus e\right)  \right)  }_{=r_{M}\left(  A\cup\left(
K\setminus e\right)  \right)  }+\underbrace{\left[  e\in K\right]
}_{\substack{=1\\\text{(since }e\in K\text{)}}}=r_{M}\left(  A\cup\left(
K\setminus e\right)  \right)  +1$, this yields $r_{M}\left(  A\cup K\right)
=r_{M\setminus e}\left(  A\cup\left(  K\setminus e\right)  \right)  +\left[
e\in K\right]  $. Thus, Lemma \ref{lem.delcon.rank.lem3} \textbf{(b)} is
proven in Case 1.

Let us now consider Case 2. In this case, we have $e\notin K$. Thus,
$K\setminus e=K$. Now,%
\[
r_{M\setminus e}\left(  A\cup\left(  K\setminus e\right)  \right)
+\underbrace{\left[  e\in K\right]  }_{\substack{=0\\\text{(since }e\notin
K\text{)}}}=r_{M\setminus e}\left(  A\cup\left(  K\setminus e\right)  \right)
=r_{M}\left(  A\cup\underbrace{\left(  K\setminus e\right)  }_{=K}\right)
=r_{M}\left(  A\cup K\right)  .
\]
Thus, Lemma \ref{lem.delcon.rank.lem3} \textbf{(b)} is proven in Case 2.

Hence, Lemma \ref{lem.delcon.rank.lem3} \textbf{(b)} is proven in each of the
two Cases 1 and 2. Thus, Lemma \ref{lem.delcon.rank.lem3} \textbf{(b)} always holds.

\textbf{(c)} Assume that $K=E$, and that $e$ is not a coloop.

If we had $r_{M}\left(  E\setminus e\right)  \neq r_{M}\left(  E\right)  $,
then the element $e$ would be a coloop (by Proposition \ref{prop.loops.equiv}
\textbf{(c)}), which would contradict the assumption that $e$ is not a coloop.
Hence, we cannot have $r_{M}\left(  E\setminus e\right)  \neq r_{M}\left(
E\right)  $. Thus, we must have $r_{M}\left(  E\setminus e\right)
=r_{M}\left(  E\right)  $.

Now, $A\subseteq E\setminus e$ (since $e\notin A$) and thus $A\cup\left(
E\setminus e\right)  =E\setminus e$. Now,%
\[
r_{M\setminus e}\left(  A\cup\left(  K\setminus e\right)  \right)
=r_{M}\left(  A\cup\left(  \underbrace{K}_{=E}\setminus e\right)  \right)
=r_{M}\left(  \underbrace{A\cup\left(  E\setminus e\right)  }_{=E\setminus
e}\right)  =r_{M}\left(  E\setminus e\right)  =r_{M}\left(  E\right)  .
\]
Compared with%
\[
r_{M}\left(  A\cup\underbrace{K}_{=E}\right)  =r_{M}\left(  \underbrace{A\cup
E}_{\substack{=E\\\text{(since }A\subseteq E\text{)}}}\right)  =r_{M}\left(
E\right)  ,
\]
this yields $r_{M}\left(  A\cup K\right)  =r_{M\setminus e}\left(
A\cup\left(  K\setminus e\right)  \right)  $. This proves Lemma
\ref{lem.delcon.rank.lem3} \textbf{(c)}.
\end{proof}

\begin{lemma}
\label{lem.delcon.rank.lem4}Let $M=\left(  E,\mathcal{I}\right)  $ be a
matroid. Let $e\in E$. Let $A\in\mathcal{P}\left(  E\right)  $ be such that
$e\notin A$. Let $K\in\mathcal{P}\left(  E\right)  $. Then,%
\[
n_{M}\left(  A\setminus K\right)  =n_{M\setminus e}\left(  A\setminus\left(
K\setminus e\right)  \right)  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.delcon.rank.lem4}.]We have $e\notin A$, hence
$A\subseteq E\setminus e$, thus $A\setminus K\subseteq A\subseteq E\setminus
e$. Hence, $A\setminus K\in\mathcal{P}\left(  E\setminus e\right)  $.

For every $S\in\mathcal{P}\left(  E\setminus e\right)  $, we have
$n_{M\setminus e}\left(  S\right)  =n_{M}\left(  S\right)  $%
\ \ \ \ \footnote{\textit{Proof.} Let $S\in\mathcal{P}\left(  E\setminus
e\right)  $. Thus, $S\in\mathcal{P}\left(  E\setminus e\right)  =\mathcal{P}%
\left(  E\setminus\left\{  e\right\}  \right)  $. Hence, Proposition
\ref{prop.delcon.rank} \textbf{(a)} (applied to $Z=\left\{  e\right\}  $)
shows that $r_{M\setminus\left\{  e\right\}  }\left(  S\right)  =r_{M}\left(
S\right)  $. Since $M\setminus\left\{  e\right\}  =M\setminus e$, this
rewrites as $r_{M\setminus e}\left(  S\right)  =r_{M}\left(  S\right)  $. The
definition of $n_{M}\left(  S\right)  $ yields $n_{M}\left(  S\right)
=\left\vert S\right\vert -r_{M}\left(  S\right)  $. But the definition of
$n_{M\setminus e}\left(  S\right)  $ yields%
\[
n_{M\setminus e}\left(  S\right)  =\left\vert S\right\vert
-\underbrace{r_{M\setminus e}\left(  S\right)  }_{=r_{M}\left(  S\right)
}=\left\vert S\right\vert -r_{M}\left(  S\right)  =n_{M}\left(  S\right)  ,
\]
qed.}. Applying this to $S=A\setminus K$, we obtain $n_{M\setminus e}\left(
A\setminus K\right)  =n_{M}\left(  A\setminus K\right)  $.

But $e\notin A$. Hence, $A\setminus\left(  K\setminus e\right)  =A\setminus
K$. Thus, $n_{M\setminus e}\left(  \underbrace{A\setminus\left(  K\setminus
e\right)  }_{=A\setminus K}\right)  =n_{M\setminus e}\left(  A\setminus
K\right)  =n_{M}\left(  A\setminus K\right)  $. This proves Lemma
\ref{lem.delcon.rank.lem4}.
\end{proof}

\begin{lemma}
\label{lem.filtutte.rec.a}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. Let $e\in E$.
Assume that $e$ is a loop.

\textbf{(a)} Let $k\in\left\{  1,2,\ldots,m\right\}  $ be such that $e\in
E_{k}\setminus E_{k-1}$. Then,%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\left(  y_{k}-1\right)  T_{\mathbf{M}/e}.
\end{align*}


\textbf{(b)} We have%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =T_{\mathbf{M}/e}.
\end{align*}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.filtutte.rec.a}.]The definition of $\mathbf{E}%
\setminus e$ shows that $\mathbf{E}\setminus e=\left(  E_{0}\setminus
e,E_{1}\setminus e,\ldots,E_{m}\setminus e\right)  $. The definition of
$\mathbf{M}/e$ shows that $\mathbf{M}/e=\left(  M/e,\mathbf{E}\setminus
e\right)  $. The matroid $M/e$ has ground set $E\setminus e$. Hence, the
definition of $T_{\mathbf{M}/e}$ yields%
\begin{align}
&  T_{\mathbf{M}/e}\nonumber\\
&  =\underbrace{\sum_{A\subseteq E\setminus e}}_{=\sum_{\substack{A\subseteq
E;\\e\notin A}}}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M/e}%
\left(  A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M/e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\right)  \left(  \prod
_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(  A\setminus\left(
E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(
E_{i}\setminus e\right)  \right)  }\right) \nonumber\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)  .
\label{pf.lem.filtutte.rec.a.TM}%
\end{align}


Since $\left(  M,\mathbf{E}\right)  $ is a filtered matroid, we have
$\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}=E$. Thus,
$E=\bigsqcup_{i=1}^{m}\left(  E_{i}\setminus E_{i-1}\right)  $. Hence, $e\in
E=\bigsqcup_{i=1}^{m}\left(  E_{i}\setminus E_{i-1}\right)  $. In other words,
there exists exactly one $i\in\left\{  1,2,\ldots,m\right\}  $ satisfying
$e\in E_{i}\setminus E_{i-1}$. This $i$ must be $k$ (since $e\in
E_{k}\setminus E_{k-1}$). Thus, for any $i\in\left\{  1,2,\ldots,m\right\}  $,
we have $e\in E_{i}\setminus E_{i-1}$ if and only if $i=k$. In other words,
for any $i\in\left\{  1,2,\ldots,m\right\}  $, we have
\begin{equation}
\left[  e\in E_{i}\setminus E_{i-1}\right]  =\left[  i=k\right]  .
\label{pf.lem.filtutte.rec.a.equiv}%
\end{equation}


\textbf{(a)} Let $A\in\mathcal{P}\left(  E\right)  $ be such that $e\notin A$.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  -r_{M}\left(
\left(  A\cup e\right)  \cup E_{i-1}\right) \nonumber\\
&  =r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.a.a.i1}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.a.a.i1}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $. Applying Lemma
\ref{lem.delcon.rank.lem1} to $K=E_{i}$, we obtain%
\begin{equation}
r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  =r_{M/e}\left(
A\cup\left(  E_{i}\setminus e\right)  \right)  +r_{M}\left(  e\right)  .
\label{pf.lem.filtutte.rec.a.a.i1.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem1} to $K=E_{i-1}$, we obtain
\[
r_{M}\left(  \left(  A\cup e\right)  \cup E_{i-1}\right)  =r_{M/e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  +r_{M}\left(  e\right)  .
\]
Subtracting this equality from (\ref{pf.lem.filtutte.rec.a.a.i1.pf.1}), we
obtain%
\begin{align*}
&  r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  -r_{M}\left(
\left(  A\cup e\right)  \cup E_{i-1}\right) \\
&  =\left(  r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
+r_{M}\left(  e\right)  \right)  -\left(  r_{M/e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  +r_{M}\left(  e\right)  \right) \\
&  =r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)  .
\end{align*}
This proves (\ref{pf.lem.filtutte.rec.a.a.i1}).}.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)
-n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right) \nonumber\\
&  =n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  +\left[
i=k\right]  \label{pf.lem.filtutte.rec.a.a.i2}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.a.a.i2}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $. Thus, $E_{i-1}\subseteq E_{i}$ (since
$E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}$).
\par
Applying Lemma \ref{lem.delcon.rank.lem2} \textbf{(c)} to $K=E_{i}$, we obtain%
\begin{equation}
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right)  =n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  +\left[  e\notin
E_{i}\right]  . \label{pf.lem.filtutte.rec.a.a.i2.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem2} \textbf{(c)} to $K=E_{i-1}$, we
obtain
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)  =n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  +\left[  e\notin
E_{i-1}\right]  .
\]
Subtracting (\ref{pf.lem.filtutte.rec.a.a.i1.pf.1}) from this equality, we
obtain%
\begin{align*}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)
-n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right) \\
&  =\left(  n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  +\left[  e\notin E_{i-1}\right]  \right)  -\left(  n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  +\left[  e\notin
E_{i}\right]  \right) \\
&  =n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)
+\underbrace{\left[  e\notin E_{i-1}\right]  -\left[  e\notin E_{i}\right]
}_{\substack{=\left[  e\in E_{i}\setminus E_{i-1}\right]  \\\text{(since
}E_{i-1}\subseteq E_{i}\text{)}}}\\
&  =n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)
+\underbrace{\left[  e\in E_{i}\setminus E_{i-1}\right]  }_{\substack{=\left[
i=k\right]  \\\text{(by (\ref{pf.lem.filtutte.rec.a.equiv}))}}}\\
&  =n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  +\left[
i=k\right]  .
\end{align*}
This proves (\ref{pf.lem.filtutte.rec.a.a.i2}).}. Thus,%
\begin{align}
&  \prod_{i=1}^{m}\underbrace{\left(  y_{i}-1\right)  ^{n_{M}\left(  \left(
A\cup e\right)  \setminus E_{i-1}\right)  -n_{M}\left(  \left(  A\cup
e\right)  \setminus E_{i}\right)  }}_{\substack{=\left(  y_{i}-1\right)
^{n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  +\left[
i=k\right]  }\\\text{(by (\ref{pf.lem.filtutte.rec.a.a.i2}))}}}\nonumber\\
&  =\prod_{i=1}^{m}\underbrace{\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  +\left[  i=k\right]  }%
}_{=\left(  y_{i}-1\right)  ^{n_{M/e}\left(  A\setminus\left(  E_{i-1}%
\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(  E_{i}\setminus
e\right)  \right)  }\left(  y_{i}-1\right)  ^{\left[  i=k\right]  }%
}\nonumber\\
&  =\prod_{i=1}^{m}\left(  \left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\left(  y_{i}-1\right)
^{\left[  i=k\right]  }\right) \nonumber\\
&  =\left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)
\underbrace{\left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{\left[
i=k\right]  }\right)  }_{\substack{=y_{k}-1\\\text{(since all factors of this
product are }1\\\text{except of the factor for }i=k\text{)}}}\nonumber\\
&  =\left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)  \left(
y_{k}-1\right)  . \label{pf.lem.filtutte.rec.a.a.i2prod}%
\end{align}


Now, the map
\[
\left\{  A\subseteq E\ \mid\ e\notin A\right\}  \rightarrow\left\{  A\subseteq
E\ \mid\ e\in A\right\}  ,\ \ \ \ \ \ \ \ \ \ A\mapsto A\cup e
\]
is a bijection. Hence, we can substitute $A\cup e$ for $A$ in the sum%
\[
\sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  .
\]
We thus obtain%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}%
^{m}\underbrace{\left(  x_{i}-1\right)  ^{r_{M}\left(  \left(  A\cup e\right)
\cup E_{i}\right)  -r_{M}\left(  \left(  A\cup e\right)  \cup E_{i-1}\right)
}}_{\substack{=\left(  x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}%
\setminus e\right)  \right)  }\\\text{(by (\ref{pf.lem.filtutte.rec.a.a.i1}%
))}}}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \underbrace{\left(  \prod_{i=1}^{m}\left(
y_{i}-1\right)  ^{n_{M}\left(  \left(  A\cup e\right)  \setminus
E_{i-1}\right)  -n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right)
}\right)  }_{\substack{=\left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)
\left(  y_{k}-1\right)  \\\text{(by (\ref{pf.lem.filtutte.rec.a.a.i2prod}))}%
}}\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)
\left(  y_{k}-1\right) \\
&  =\left(  y_{k}-1\right)  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(
\prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}%
\setminus e\right)  \right)  }\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)
\\
&  =\left(  y_{k}-1\right)  T_{\mathbf{M}/e}%
\end{align*}
(this follows by multiplying both sides of the equality
(\ref{pf.lem.filtutte.rec.a.TM}) by $y_{k}-1$). This proves Lemma
\ref{lem.filtutte.rec.a} \textbf{(a)}.

\textbf{(b) }Let $A\in\mathcal{P}\left(  E\right)  $ be such that $e\notin A$.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
\nonumber\\
&  =r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.a.b.i1}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.a.b.i1}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $. Applying Lemma
\ref{lem.delcon.rank.lem3} \textbf{(a)} to $K=E_{i}$, we obtain%
\begin{equation}
r_{M}\left(  A\cup E_{i}\right)  =r_{M\setminus e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  . \label{pf.lem.filtutte.rec.a.b.i1.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem3} \textbf{(a)} to $K=E_{i-1}$, we
obtain
\[
r_{M}\left(  A\cup E_{i-1}\right)  =r_{M\setminus e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  .
\]
Subtracting this equality from (\ref{pf.lem.filtutte.rec.a.b.i1.pf.1}), we
obtain%
\[
r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
=r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)  .
\]
This proves (\ref{pf.lem.filtutte.rec.a.b.i1}).}.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right) \nonumber\\
&  =n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)
\right)  \label{pf.lem.filtutte.rec.a.b.i2}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.a.b.i2}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $.
\par
Applying Lemma \ref{lem.delcon.rank.lem4} to $K=E_{i}$, we obtain%
\begin{equation}
n_{M}\left(  A\setminus E_{i}\right)  =n_{M\setminus e}\left(  A\setminus
\left(  E_{i}\setminus e\right)  \right)  .
\label{pf.lem.filtutte.rec.a.b.i2.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem4} to $K=E_{i-1}$, we obtain
\[
n_{M}\left(  A\setminus E_{i-1}\right)  =n_{M\setminus e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  .
\]
Subtracting (\ref{pf.lem.filtutte.rec.a.b.i1.pf.1}) from this equality, we
obtain%
\[
n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)
=n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)
.
\]
This proves (\ref{pf.lem.filtutte.rec.a.b.i2}).}.

But Proposition \ref{prop.delcon.del=con} \textbf{(a)} shows that
$M/e=M\setminus e$. Now,%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}%
^{m}\underbrace{\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)
-r_{M}\left(  A\cup E_{i-1}\right)  }}_{\substack{=\left(  x_{i}-1\right)
^{r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\\\text{(by (\ref{pf.lem.filtutte.rec.a.b.i1}))}}}\right)  \left(
\prod_{i=1}^{m}\underbrace{\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }}_{\substack{=\left(
y_{i}-1\right)  ^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus
e\right)  \right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus
e\right)  \right)  }\\\text{(by (\ref{pf.lem.filtutte.rec.a.b.i2}))}}}\right)
\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus
e\right)  \right)  -r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus
e\right)  \right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)
\right)  }\right) \\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }M\setminus e=M/e\right) \\
&  =T_{\mathbf{M}/e}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.lem.filtutte.rec.a.TM})}\right)  .
\end{align*}
This proves Lemma \ref{lem.filtutte.rec.a} \textbf{(b)}.
\end{proof}

\begin{lemma}
\label{lem.filtutte.rec.b}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. Let $e\in E$.
Assume that $e$ is a coloop.

\textbf{(a)} We have
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =T_{\mathbf{M}/e}.
\end{align*}


\textbf{(b)} Let $k\in\left\{  1,2,\ldots,m\right\}  $ be such that $e\in
E_{k}\setminus E_{k-1}$. Then,%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\left(  x_{k}-1\right)  T_{\mathbf{M}/e}.
\end{align*}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.filtutte.rec.b}.]The definition of $\mathbf{E}%
\setminus e$ shows that $\mathbf{E}\setminus e=\left(  E_{0}\setminus
e,E_{1}\setminus e,\ldots,E_{m}\setminus e\right)  $. The definition of
$\mathbf{M}/e$ shows that $\mathbf{M}/e=\left(  M/e,\mathbf{E}\setminus
e\right)  $. The matroid $M/e$ has ground set $E\setminus e$. Hence, the
definition of $T_{\mathbf{M}/e}$ yields%
\begin{align}
&  T_{\mathbf{M}/e}\nonumber\\
&  =\underbrace{\sum_{A\subseteq E\setminus e}}_{=\sum_{\substack{A\subseteq
E;\\e\notin A}}}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M/e}%
\left(  A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M/e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\right)  \left(  \prod
_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(  A\setminus\left(
E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(
E_{i}\setminus e\right)  \right)  }\right) \nonumber\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)  .
\label{pf.lem.filtutte.rec.b.TM}%
\end{align}


Since $\left(  M,\mathbf{E}\right)  $ is a filtered matroid, we have
$\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}=E$. Thus,
$E=\bigsqcup_{i=1}^{m}\left(  E_{i}\setminus E_{i-1}\right)  $. Hence, $e\in
E=\bigsqcup_{i=1}^{m}\left(  E_{i}\setminus E_{i-1}\right)  $. In other words,
there exists exactly one $i\in\left\{  1,2,\ldots,m\right\}  $ satisfying
$e\in E_{i}\setminus E_{i-1}$. This $i$ must be $k$ (since $e\in
E_{k}\setminus E_{k-1}$). Thus, for any $i\in\left\{  1,2,\ldots,m\right\}  $,
we have $e\in E_{i}\setminus E_{i-1}$ if and only if $i=k$. In other words,
for any $i\in\left\{  1,2,\ldots,m\right\}  $, we have
\begin{equation}
\left[  e\in E_{i}\setminus E_{i-1}\right]  =\left[  i=k\right]  .
\label{pf.lem.filtutte.rec.b.equiv}%
\end{equation}


\textbf{(a)} Let $A\in\mathcal{P}\left(  E\right)  $ be such that $e\notin A$.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  -r_{M}\left(
\left(  A\cup e\right)  \cup E_{i-1}\right) \nonumber\\
&  =r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.b.a.i1}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.b.a.i1}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $. Applying Lemma
\ref{lem.delcon.rank.lem1} to $K=E_{i}$, we obtain%
\begin{equation}
r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  =r_{M/e}\left(
A\cup\left(  E_{i}\setminus e\right)  \right)  +r_{M}\left(  e\right)  .
\label{pf.lem.filtutte.rec.b.a.i1.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem1} to $K=E_{i-1}$, we obtain
\[
r_{M}\left(  \left(  A\cup e\right)  \cup E_{i-1}\right)  =r_{M/e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  +r_{M}\left(  e\right)  .
\]
Subtracting this equality from (\ref{pf.lem.filtutte.rec.b.a.i1.pf.1}), we
obtain%
\begin{align*}
&  r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  -r_{M}\left(
\left(  A\cup e\right)  \cup E_{i-1}\right) \\
&  =\left(  r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
+r_{M}\left(  e\right)  \right)  -\left(  r_{M/e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  +r_{M}\left(  e\right)  \right) \\
&  =r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)  .
\end{align*}
This proves (\ref{pf.lem.filtutte.rec.b.a.i1}).}.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)
-n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right) \nonumber\\
&  =n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.b.a.i2}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.b.a.i2}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $.
\par
Applying Lemma \ref{lem.delcon.rank.lem2} \textbf{(d)} to $K=E_{i}$, we obtain%
\begin{equation}
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right)  =n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  .
\label{pf.lem.filtutte.rec.b.a.i2.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem2} \textbf{(d)} to $K=E_{i-1}$, we
obtain
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)  =n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  .
\]
Subtracting (\ref{pf.lem.filtutte.rec.b.a.i1.pf.1}) from this equality, we
obtain%
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)  -n_{M}\left(
\left(  A\cup e\right)  \setminus E_{i}\right)  =n_{M/e}\left(  A\setminus
\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(
E_{i}\setminus e\right)  \right)  .
\]
This proves (\ref{pf.lem.filtutte.rec.b.a.i2}).}.

Now, the map
\[
\left\{  A\subseteq E\ \mid\ e\notin A\right\}  \rightarrow\left\{  A\subseteq
E\ \mid\ e\in A\right\}  ,\ \ \ \ \ \ \ \ \ \ A\mapsto A\cup e
\]
is a bijection. Hence, we can substitute $A\cup e$ for $A$ in the sum%
\[
\sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  .
\]
We thus obtain%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}%
^{m}\underbrace{\left(  x_{i}-1\right)  ^{r_{M}\left(  \left(  A\cup e\right)
\cup E_{i}\right)  -r_{M}\left(  \left(  A\cup e\right)  \cup E_{i-1}\right)
}}_{\substack{=\left(  x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}%
\setminus e\right)  \right)  }\\\text{(by (\ref{pf.lem.filtutte.rec.b.a.i1}%
))}}}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\underbrace{\left(
y_{i}-1\right)  ^{n_{M}\left(  \left(  A\cup e\right)  \setminus
E_{i-1}\right)  -n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right)
}}_{\substack{=\left(  y_{i}-1\right)  ^{n_{M/e}\left(  A\setminus\left(
E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(
E_{i}\setminus e\right)  \right)  }\\\text{(by
(\ref{pf.lem.filtutte.rec.b.a.i2}))}}}\right) \\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)
\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right) \\
&  =T_{\mathbf{M}/e}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.lem.filtutte.rec.b.TM})}\right)
\end{align*}
$\allowbreak$This proves Lemma \ref{lem.filtutte.rec.b} \textbf{(a)}.

\textbf{(b) }Let $A\in\mathcal{P}\left(  E\right)  $ be such that $e\notin A$.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
\nonumber\\
&  =r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
+\left[  i=k\right]  \label{pf.lem.filtutte.rec.b.b.i1}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.b.b.i1}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $. Thus, $E_{i-1}\subseteq E_{i}$ (since
$E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}$).
\par
Applying Lemma \ref{lem.delcon.rank.lem3} \textbf{(b)} to $K=E_{i}$, we obtain%
\begin{equation}
r_{M}\left(  A\cup E_{i}\right)  =r_{M\setminus e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  +\left[  e\in E_{i}\right]  .
\label{pf.lem.filtutte.rec.b.b.i1.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem3} \textbf{(a)} to $K=E_{i-1}$, we
obtain
\[
r_{M}\left(  A\cup E_{i-1}\right)  =r_{M\setminus e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  +\left[  e\in E_{i-1}\right]  .
\]
Subtracting this equality from (\ref{pf.lem.filtutte.rec.b.b.i1.pf.1}), we
obtain%
\begin{align*}
&  r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right) \\
&  =\left(  r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  +\left[  e\in E_{i}\right]  \right)  -\left(  r_{M\setminus e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  +\left[  e\in E_{i-1}\right]
\right) \\
&  =r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
+\underbrace{\left[  e\in E_{i}\right]  -\left[  e\in E_{i-1}\right]
}_{\substack{=\left[  e\in E_{i}\setminus E_{i-1}\right]  \\\text{(since
}E_{i-1}\subseteq E_{i}\text{)}}}\\
&  =r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
+\underbrace{\left[  e\in E_{i}\setminus E_{i-1}\right]  }_{\substack{=\left[
i=k\right]  \\\text{(by (\ref{pf.lem.filtutte.rec.b.equiv}))}}}\\
&  =r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
+\left[  i=k\right]  .
\end{align*}
This proves (\ref{pf.lem.filtutte.rec.b.b.i1}).}. Thus,%
\begin{align}
&  \prod_{i=1}^{m}\underbrace{\left(  x_{i}-1\right)  ^{n_{M}\left(  \left(
A\cup e\right)  \setminus E_{i-1}\right)  -n_{M}\left(  \left(  A\cup
e\right)  \setminus E_{i}\right)  }}_{\substack{=\left(  x_{i}-1\right)
^{r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
+\left[  i=k\right]  }\\\text{(by (\ref{pf.lem.filtutte.rec.b.b.i1}))}%
}}\nonumber\\
&  =\prod_{i=1}^{m}\underbrace{\left(  x_{i}-1\right)  ^{r_{M\setminus
e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M\setminus
e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)  +\left[
i=k\right]  }}_{=\left(  x_{i}-1\right)  ^{r_{M\setminus e}\left(
A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M\setminus e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\left(  x_{i}-1\right)
^{\left[  i=k\right]  }}\nonumber\\
&  =\prod_{i=1}^{m}\left(  \left(  x_{i}-1\right)  ^{r_{M\setminus e}\left(
A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M\setminus e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\left(  x_{i}-1\right)
^{\left[  i=k\right]  }\right) \nonumber\\
&  =\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M\setminus e}\left(
A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M\setminus e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\right)  \underbrace{\left(
\prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{\left[  i=k\right]  }\right)
}_{\substack{=x_{k}-1\\\text{(since all factors of this product are
}1\\\text{except of the factor for }i=k\text{)}}}\nonumber\\
&  =\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M\setminus e}\left(
A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M\setminus e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\right)  \left(
x_{k}-1\right)  . \label{pf.lem.filtutte.rec.b.b.i1prod}%
\end{align}


For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right) \nonumber\\
&  =n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)
\right)  \label{pf.lem.filtutte.rec.b.b.i2}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.b.b.i2}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $.
\par
Applying Lemma \ref{lem.delcon.rank.lem4} to $K=E_{i}$, we obtain%
\begin{equation}
n_{M}\left(  A\setminus E_{i}\right)  =n_{M\setminus e}\left(  A\setminus
\left(  E_{i}\setminus e\right)  \right)  .
\label{pf.lem.filtutte.rec.b.b.i2.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem4} to $K=E_{i-1}$, we obtain
\[
n_{M}\left(  A\setminus E_{i-1}\right)  =n_{M\setminus e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  .
\]
Subtracting (\ref{pf.lem.filtutte.rec.b.b.i1.pf.1}) from this equality, we
obtain%
\[
n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)
=n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)
.
\]
This proves (\ref{pf.lem.filtutte.rec.b.b.i2}).}.

But Proposition \ref{prop.delcon.del=con} \textbf{(a)} shows that
$M/e=M\setminus e$. Now,%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\notin A}}\underbrace{\left(  \prod
_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)
-r_{M}\left(  A\cup E_{i-1}\right)  }\right)  }_{\substack{=\left(
\prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M\setminus e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  -r_{M\setminus e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  }\right)  \left(  x_{k}-1\right)
\\\text{(by (\ref{pf.lem.filtutte.rec.b.b.i1prod}))}}}\left(  \prod_{i=1}%
^{m}\underbrace{\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }}_{\substack{=\left(
y_{i}-1\right)  ^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus
e\right)  \right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus
e\right)  \right)  }\\\text{(by (\ref{pf.lem.filtutte.rec.b.b.i2}))}}}\right)
\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus
e\right)  \right)  -r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus
e\right)  \right)  }\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  x_{k}-1\right)  \left(  \prod_{i=1}^{m}\left(
y_{i}-1\right)  ^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus
e\right)  \right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus
e\right)  \right)  }\right) \\
&  =\left(  x_{k}-1\right)  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(
\prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M\setminus e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  -r_{M\setminus e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  }\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)
\right)  }\right) \\
&  =\left(  x_{k}-1\right)  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(
\prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}%
\setminus e\right)  \right)  }\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)
\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }M\setminus e=M/e\right) \\
&  =\left(  x_{k}-1\right)  T_{\mathbf{M}/e}%
\end{align*}
(this follows by multiplying both sides of the equality
(\ref{pf.lem.filtutte.rec.b.TM}) by $x_{k}-1$). This proves Lemma
\ref{lem.filtutte.rec.b} \textbf{(b)}.
\end{proof}

\begin{lemma}
\label{lem.filtutte.rec.c}Let $\mathbf{M}=\left(  M,\mathbf{E}\right)  $ be a
filtered matroid, with $M=\left(  E,\mathcal{I}\right)  $. Write the list
$\mathbf{E}$ as $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. Let $e\in E$ be
such that $e\in E_{m}\setminus E_{m-1}$. Assume that $e$ is neither a loop nor
a coloop.

\textbf{(a)} We have
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =T_{\mathbf{M}/e}.
\end{align*}


\textbf{(b)} We have%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =T_{\mathbf{M}\setminus e}.
\end{align*}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.filtutte.rec.c}.]Since $\left(  M,\mathbf{E}\right)
$ is a filtered matroid, we have $\varnothing=E_{0}\subseteq E_{1}%
\subseteq\cdots\subseteq E_{m}=E$.

But from $e\in E_{m}\setminus E_{m-1}\notin E_{m-1}$, we obtain%
\begin{equation}
e\notin E_{j}\ \ \ \ \ \ \ \ \ \ \text{for every }j\in\left\{  0,1,\ldots
,m-1\right\}  \label{pf.lem.filtutte.rec.c.nothere}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.c.nothere}):} Let
$j\in\left\{  0,1,\ldots,m-1\right\}  $. Thus, $j\leq m-1$, so that
$E_{j}\subseteq E_{m-1}$ (since $E_{0}\subseteq E_{1}\subseteq\cdots\subseteq
E_{m}$). Thus, $e\notin E_{j}$ (since $e\notin E_{m-1}$). This proves
(\ref{pf.lem.filtutte.rec.c.nothere}).}.

Proposition \ref{prop.loops.equiv} \textbf{(a)} shows that the element $e$ is
a loop (of $M$) if and only if $r_{M}\left(  e\right)  =0$. Thus, we don't
have $r_{M}\left(  e\right)  =0$ (since $e$ is not a loop). In other words, we
have $r_{M}\left(  e\right)  \neq0$. Consequently, $r_{M}\left(  e\right)
=1$\ \ \ \ \footnote{\textit{Proof.} Applying (\ref{eq.def.rank.upperbd}) to
$S=\left\{  e\right\}  $, we obtain $r_{M}\left(  \left\{  e\right\}  \right)
\leq\left\vert \left\{  e\right\}  \right\vert =1$. Thus, $r_{M}\left(
e\right)  =r_{M}\left(  \left\{  e\right\}  \right)  \leq1$. Combining this
with $r_{M}\left(  e\right)  \neq0$, we obtain $r_{M}\left(  e\right)  =1$,
qed.}.

The definition of $\mathbf{E}\setminus e$ shows that $\mathbf{E}\setminus
e=\left(  E_{0}\setminus e,E_{1}\setminus e,\ldots,E_{m}\setminus e\right)  $.
The definition of $\mathbf{M}/e$ shows that $\mathbf{M}/e=\left(
M/e,\mathbf{E}\setminus e\right)  $. The matroid $M/e$ has ground set
$E\setminus e$. Hence, the definition of $T_{\mathbf{M}/e}$ yields%

\begin{align}
&  T_{\mathbf{M}/e}\nonumber\\
&  =\underbrace{\sum_{A\subseteq E\setminus e}}_{=\sum_{\substack{A\subseteq
E;\\e\notin A}}}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M/e}%
\left(  A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M/e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\right)  \left(  \prod
_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(  A\setminus\left(
E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(
E_{i}\setminus e\right)  \right)  }\right) \nonumber\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)  .
\label{pf.lem.filtutte.rec.c.TM1}%
\end{align}


The definition of $\mathbf{E}\setminus e$ shows that $\mathbf{E}\setminus
e=\left(  E_{0}\setminus e,E_{1}\setminus e,\ldots,E_{m}\setminus e\right)  $.
The definition of $\mathbf{M}\setminus e$ shows that $\mathbf{M}/e=\left(
M\setminus e,\mathbf{E}\setminus e\right)  $. The matroid $M\setminus e$ has
ground set $E\setminus e$. Hence, the definition of $T_{\mathbf{M}\setminus
e}$ yields%
\begin{align}
&  T_{\mathbf{M}\setminus e}\nonumber\\
&  =\underbrace{\sum_{A\subseteq E\setminus e}}_{=\sum_{\substack{A\subseteq
E;\\e\notin A}}}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M\setminus
e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)  -r_{M\setminus
e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)  }\right)  \left(
\prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M\setminus e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M\setminus e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right) \nonumber\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus
e\right)  \right)  -r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus
e\right)  \right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)
\right)  }\right)  . \label{pf.lem.filtutte.rec.c.TM2}%
\end{align}


\textbf{(a)} Let $A\in\mathcal{P}\left(  E\right)  $ be such that $e\notin A$.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  -r_{M}\left(
\left(  A\cup e\right)  \cup E_{i-1}\right) \nonumber\\
&  =r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.c.a.i1}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.c.a.i1}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $. Applying Lemma
\ref{lem.delcon.rank.lem1} to $K=E_{i}$, we obtain%
\begin{equation}
r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  =r_{M/e}\left(
A\cup\left(  E_{i}\setminus e\right)  \right)  +r_{M}\left(  e\right)  .
\label{pf.lem.filtutte.rec.c.a.i1.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem1} to $K=E_{i-1}$, we obtain
\[
r_{M}\left(  \left(  A\cup e\right)  \cup E_{i-1}\right)  =r_{M/e}\left(
A\cup\left(  E_{i-1}\setminus e\right)  \right)  +r_{M}\left(  e\right)  .
\]
Subtracting this equality from (\ref{pf.lem.filtutte.rec.c.a.i1.pf.1}), we
obtain%
\begin{align*}
&  r_{M}\left(  \left(  A\cup e\right)  \cup E_{i}\right)  -r_{M}\left(
\left(  A\cup e\right)  \cup E_{i-1}\right) \\
&  =\left(  r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
+r_{M}\left(  e\right)  \right)  -\left(  r_{M/e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  +r_{M}\left(  e\right)  \right) \\
&  =r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)  .
\end{align*}
This proves (\ref{pf.lem.filtutte.rec.c.a.i1}).}.

Every $j\in\left\{  0,1,\ldots,m\right\}  $ satisfies%
\begin{equation}
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{j}\right)  =n_{M/e}\left(
A\setminus\left(  E_{j}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.c.a.j2}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.c.a.j2}):} Let
$j\in\left\{  0,1,\ldots,m\right\}  $. We must prove
(\ref{pf.lem.filtutte.rec.c.a.j2}). We are in one of the following two cases:
\par
\textit{Case 1:} We have $j<m$.
\par
\textit{Case 2:} We have $j=m$.
\par
Let us first consider Case 1. In this case, we have $j<m$. Hence,
$j\in\left\{  0,1,\ldots,m\right\}  $, so that $e\notin E_{j}$ (by
(\ref{pf.lem.filtutte.rec.c.nothere})). Hence, Lemma
\ref{lem.delcon.rank.lem2} \textbf{(b)} (applied to $K=E_{j}$) shows that%
\begin{align*}
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{j}\right)   &
=n_{M/e}\left(  A\setminus\left(  E_{j}\setminus e\right)  \right)
+1-\underbrace{r_{M}\left(  e\right)  }_{=1}\\
&  =n_{M/e}\left(  A\setminus\left(  E_{j}\setminus e\right)  \right)
+1-1=n_{M/e}\left(  A\setminus\left(  E_{j}\setminus e\right)  \right)  .
\end{align*}
Thus, (\ref{pf.lem.filtutte.rec.c.a.j2}) is proven in Case 1.
\par
Let us now consider Case 2. In this case, we have $j=m$. Thus, $E_{j}=E_{m}%
=E$. Hence, Lemma \ref{lem.delcon.rank.lem2} \textbf{(e)} (applied to
$K=E_{j}$) shows that $n_{M}\left(  \left(  A\cup e\right)  \setminus
E_{j}\right)  =n_{M/e}\left(  A\setminus\left(  E_{j}\setminus e\right)
\right)  $. Thus, (\ref{pf.lem.filtutte.rec.c.a.j2}) is proven in Case 2.
\par
We have thus proven (\ref{pf.lem.filtutte.rec.c.a.j2}) in each of the two
Cases 1 and 2. Hence, (\ref{pf.lem.filtutte.rec.c.a.j2}) always holds.}.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)
-n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right) \nonumber\\
&  =n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.c.a.i2}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.c.a.i2}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $.
\par
Applying (\ref{pf.lem.filtutte.rec.c.a.j2}) to $j=i$, we obtain%
\begin{equation}
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right)  =n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  .
\label{pf.lem.filtutte.rec.c.a.i2.pf.1}%
\end{equation}
Applying (\ref{pf.lem.filtutte.rec.c.a.j2}) to $j=i-1$, we obtain
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)  =n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  .
\]
Subtracting (\ref{pf.lem.filtutte.rec.c.a.i1.pf.1}) from this equality, we
obtain%
\[
n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i-1}\right)  -n_{M}\left(
\left(  A\cup e\right)  \setminus E_{i}\right)  =n_{M/e}\left(  A\setminus
\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(
E_{i}\setminus e\right)  \right)  .
\]
This proves (\ref{pf.lem.filtutte.rec.c.a.i2}).}.

Now, the map
\[
\left\{  A\subseteq E\ \mid\ e\notin A\right\}  \rightarrow\left\{  A\subseteq
E\ \mid\ e\in A\right\}  ,\ \ \ \ \ \ \ \ \ \ A\mapsto A\cup e
\]
is a bijection. Hence, we can substitute $A\cup e$ for $A$ in the sum%
\[
\sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  .
\]
We thus obtain%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}%
^{m}\underbrace{\left(  x_{i}-1\right)  ^{r_{M}\left(  \left(  A\cup e\right)
\cup E_{i}\right)  -r_{M}\left(  \left(  A\cup e\right)  \cup E_{i-1}\right)
}}_{\substack{=\left(  x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}%
\setminus e\right)  \right)  }\\\text{(by (\ref{pf.lem.filtutte.rec.c.a.i1}%
))}}}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\underbrace{\left(
y_{i}-1\right)  ^{n_{M}\left(  \left(  A\cup e\right)  \setminus
E_{i-1}\right)  -n_{M}\left(  \left(  A\cup e\right)  \setminus E_{i}\right)
}}_{\substack{=\left(  y_{i}-1\right)  ^{n_{M/e}\left(  A\setminus\left(
E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(  A\setminus\left(
E_{i}\setminus e\right)  \right)  }\\\text{(by
(\ref{pf.lem.filtutte.rec.c.a.i2}))}}}\right) \\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M/e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M/e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right)
\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M/e}\left(  A\cup\left(  E_{i}\setminus e\right)
\right)  -r_{M/e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M/e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  -n_{M/e}\left(
A\setminus\left(  E_{i}\setminus e\right)  \right)  }\right) \\
&  =T_{\mathbf{M}/e}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.lem.filtutte.rec.c.TM1})}\right)
\end{align*}
$\allowbreak$This proves Lemma \ref{lem.filtutte.rec.c} \textbf{(a)}.

\textbf{(b) }Let $A\in\mathcal{P}\left(  E\right)  $ be such that $e\notin A$.

Every $j\in\left\{  0,1,\ldots,m\right\}  $ satisfies%
\begin{equation}
r_{M}\left(  A\cup E_{j}\right)  =r_{M\setminus e}\left(  A\cup\left(
E_{j}\setminus e\right)  \right)  \label{pf.lem.filtutte.rec.c.b.j1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.c.b.j1}):} Let
$j\in\left\{  0,1,\ldots,m\right\}  $. We must prove
(\ref{pf.lem.filtutte.rec.c.b.j1}). We are in one of the following two cases:
\par
\textit{Case 1:} We have $j<m$.
\par
\textit{Case 2:} We have $j=m$.
\par
Let us first consider Case 1. In this case, we have $j<m$. Hence,
$j\in\left\{  0,1,\ldots,m\right\}  $, so that $e\notin E_{j}$ (by
(\ref{pf.lem.filtutte.rec.c.nothere})). Hence, $E_{j}\setminus e=E_{j}$.
\par
But combining $A\subseteq E\setminus e$ (since $e\notin A$) with
$E_{j}\subseteq E\setminus e$ (since $e\notin E_{j}$), we obtain $A\cup
E_{j}\subseteq E\setminus e$, thus $A\cup E_{j}\in\mathcal{P}\left(
E\setminus e\right)  $. Hence, Proposition \ref{prop.delcon.rank} \textbf{(a)}
(applied to $Z=\left\{  e\right\}  $ and $S=A\cup E_{j}$) shows that
$r_{M\setminus\left\{  e\right\}  }\left(  A\cup E_{j}\right)  =r_{M}\left(
A\cup E_{j}\right)  $. Since $M\setminus\left\{  e\right\}  =M\setminus e$,
this rewrites as $r_{M\setminus e}\left(  A\cup E_{j}\right)  =r_{M}\left(
A\cup E_{j}\right)  $. Thus, $r_{M}\left(  A\cup E_{j}\right)  =r_{M\setminus
e}\left(  A\cup\underbrace{E_{j}}_{=E_{j}\setminus e}\right)  =r_{M\setminus
e}\left(  A\cup\left(  E_{j}\setminus e\right)  \right)  $. Hence,
(\ref{pf.lem.filtutte.rec.c.b.j1}) is proven in Case 1.
\par
Let us now consider Case 2. In this case, we have $j=m$. Thus, $E_{j}=E_{m}%
=E$. Hence, Lemma \ref{lem.delcon.rank.lem3} \textbf{(c)} (applied to
$K=E_{j}$) shows that $r_{M}\left(  A\cup E_{j}\right)  =r_{M\setminus
e}\left(  A\cup\left(  E_{j}\setminus e\right)  \right)  $ (since $e$ is not a
coloop). Thus, (\ref{pf.lem.filtutte.rec.c.b.j1}) is proven in Case 2.
\par
We have thus proven (\ref{pf.lem.filtutte.rec.c.b.j1}) in each of the two
Cases 1 and 2. Hence, (\ref{pf.lem.filtutte.rec.c.b.j1}) always holds.}.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
\nonumber\\
&  =r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
\label{pf.lem.filtutte.rec.c.b.i1}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.c.b.i1}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $.
\par
Applying (\ref{pf.lem.filtutte.rec.c.b.j1}) to $j=i$, we obtain%
\begin{equation}
r_{M}\left(  A\cup E_{i}\right)  =r_{M\setminus e}\left(  A\cup\left(
E_{i}\setminus e\right)  \right)  . \label{pf.lem.filtutte.rec.c.b.i1.pf.1}%
\end{equation}
Applying (\ref{pf.lem.filtutte.rec.c.b.j1}) to $j=i-1$, we obtain
\[
r_{M}\left(  A\cup E_{i-1}\right)  =r_{M\setminus e}\left(  A\cup\left(
E_{i-1}\setminus e\right)  \right)  .
\]
Subtracting this equality from (\ref{pf.lem.filtutte.rec.c.b.i1.pf.1}), we
obtain%
\[
r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
=r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)  .
\]
This proves (\ref{pf.lem.filtutte.rec.c.b.i1}).}.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, we have%
\begin{align}
&  n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right) \nonumber\\
&  =n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)
\right)  \label{pf.lem.filtutte.rec.c.b.i2}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.lem.filtutte.rec.c.b.i2}):} Let
$i\in\left\{  1,2,\ldots,m\right\}  $.
\par
Applying Lemma \ref{lem.delcon.rank.lem4} to $K=E_{i}$, we obtain%
\begin{equation}
n_{M}\left(  A\setminus E_{i}\right)  =n_{M\setminus e}\left(  A\setminus
\left(  E_{i}\setminus e\right)  \right)  .
\label{pf.lem.filtutte.rec.c.b.i2.pf.1}%
\end{equation}
Applying Lemma \ref{lem.delcon.rank.lem4} to $K=E_{i-1}$, we obtain
\[
n_{M}\left(  A\setminus E_{i-1}\right)  =n_{M\setminus e}\left(
A\setminus\left(  E_{i-1}\setminus e\right)  \right)  .
\]
Subtracting (\ref{pf.lem.filtutte.rec.c.b.i1.pf.1}) from this equality, we
obtain%
\[
n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)
=n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)  \right)
-n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)  \right)
.
\]
This proves (\ref{pf.lem.filtutte.rec.c.b.i2}).}.

Now,%
\begin{align*}
&  \sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}%
^{m}\underbrace{\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)
-r_{M}\left(  A\cup E_{i-1}\right)  }}_{\substack{=\left(  x_{i}-1\right)
^{r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus e\right)  \right)
-r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus e\right)  \right)
}\\\text{(by (\ref{pf.lem.filtutte.rec.c.b.i1}))}}}\right)  \left(
\prod_{i=1}^{m}\underbrace{\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }}_{\substack{=\left(
y_{i}-1\right)  ^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus
e\right)  \right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus
e\right)  \right)  }\\\text{(by (\ref{pf.lem.filtutte.rec.c.b.i2}))}}}\right)
\\
&  =\sum_{\substack{A\subseteq E;\\e\notin A}}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M\setminus e}\left(  A\cup\left(  E_{i}\setminus
e\right)  \right)  -r_{M\setminus e}\left(  A\cup\left(  E_{i-1}\setminus
e\right)  \right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M\setminus e}\left(  A\setminus\left(  E_{i-1}\setminus e\right)
\right)  -n_{M\setminus e}\left(  A\setminus\left(  E_{i}\setminus e\right)
\right)  }\right) \\
&  =T_{\mathbf{M}\setminus e}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.lem.filtutte.rec.c.TM2})}\right)  .
\end{align*}
This proves Lemma \ref{lem.filtutte.rec.c} \textbf{(b)}.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.filtutte.rec}.]\textbf{(a)} Assume that $e$ is
a loop. Let $k\in\left\{  1,2,\ldots,m\right\}  $ be such that $e\in
E_{k}\setminus E_{k-1}$. We need to show that $T_{\mathbf{M}}=y_{k}%
T_{\mathbf{M}\setminus e}$.

Proposition \ref{prop.delcon.del=con} \textbf{(a)} shows that $M/e=M\setminus
e$. The definition of $\mathbf{M}/e$ shows that $\mathbf{M}/e=\left(
M/e,\mathbf{E}\setminus e\right)  $. Similarly, $\mathbf{M}\setminus e=\left(
M\setminus e,\mathbf{E}\setminus e\right)  $. Hence, $\mathbf{M}/e=\left(
\underbrace{M/e}_{=M\setminus e},\mathbf{E}\setminus e\right)  =\left(
M\setminus e,\mathbf{E}\setminus e\right)  =\mathbf{M}\setminus e$.

The definition of $T_{\mathbf{M}}$ shows that%
\begin{align*}
T_{\mathbf{M}}  &  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\underbrace{\sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}%
^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(
A\cup E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  }_{\substack{=\left(  y_{k}-1\right)  T_{\mathbf{M}%
/e}\\\text{(by Lemma \ref{lem.filtutte.rec.a} \textbf{(a)})}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\sum_{\substack{A\subseteq E;\\e\notin
A}}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup
E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  }\right)  \left(
\prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right)
}_{\substack{=T_{\mathbf{M}/e}\\\text{(by Lemma \ref{lem.filtutte.rec.a}
\textbf{(b)})}}}\\
&  =\left(  y_{k}-1\right)  T_{\mathbf{M}/e}+T_{\mathbf{M}/e}=y_{k}%
T_{\mathbf{M}/e}=y_{k}T_{\mathbf{M}\setminus e}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }\mathbf{M}/e=\mathbf{M}\setminus e\right)  .
\end{align*}
This proves Proposition \ref{prop.filtutte.rec} \textbf{(a)}.

\textbf{(b)} Assume that $e$ is a coloop. Let $k\in\left\{  1,2,\ldots
,m\right\}  $ be such that $e\in E_{k}\setminus E_{k-1}$. We need to show that
$T_{\mathbf{M}}=x_{k}T_{\mathbf{M}/e}$.

The definition of $T_{\mathbf{M}}$ shows that%
\begin{align*}
T_{\mathbf{M}}  &  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\underbrace{\sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}%
^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(
A\cup E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  }_{\substack{=T_{\mathbf{M}/e}\\\text{(by Lemma
\ref{lem.filtutte.rec.b} \textbf{(a)})}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\sum_{\substack{A\subseteq E;\\e\notin
A}}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup
E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  }\right)  \left(
\prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right)
}_{\substack{=\left(  x_{k}-1\right)  T_{\mathbf{M}/e}\\\text{(by Lemma
\ref{lem.filtutte.rec.b} \textbf{(b)})}}}\\
&  =T_{\mathbf{M}/e}+\left(  x_{k}-1\right)  T_{\mathbf{M}/e}=x_{k}%
T_{\mathbf{M}/e}.
\end{align*}
This proves Proposition \ref{prop.filtutte.rec} \textbf{(b)}.

\textbf{(c)} Assume that $e$ belongs to $E_{m}\setminus E_{m-1}$ and is
neither a loop nor a coloop. The definition of $T_{\mathbf{M}}$ shows that%
\begin{align*}
T_{\mathbf{M}}  &  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right) \\
&  =\underbrace{\sum_{\substack{A\subseteq E;\\e\in A}}\left(  \prod_{i=1}%
^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(
A\cup E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  }_{\substack{=T_{\mathbf{M}/e}\\\text{(by Lemma
\ref{lem.filtutte.rec.c} \textbf{(a)})}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\sum_{\substack{A\subseteq E;\\e\notin
A}}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{r_{M}\left(  A\cup
E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)  }\right)  \left(
\prod_{i=1}^{m}\left(  y_{i}-1\right)  ^{n_{M}\left(  A\setminus
E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right)
}_{\substack{=T_{\mathbf{M}\setminus e}\\\text{(by Lemma
\ref{lem.filtutte.rec.c} \textbf{(b)})}}}\\
&  =T_{\mathbf{M}/e}+T_{\mathbf{M}\setminus e}=T_{\mathbf{M}\setminus
e}+T_{\mathbf{M}/e}.
\end{align*}
This proves Proposition \ref{prop.filtutte.rec} \textbf{(c)}.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.filtutte.pos}.]Let $E$ denote the ground set
of $M$ (so that $M=\left(  E,\mathcal{I}\right)  $ for some $\mathcal{I}%
\subseteq\mathcal{P}\left(  E\right)  $). We shall prove Proposition
\ref{prop.filtutte.pos} by induction on $m+\left\vert E\right\vert $. The
\textit{induction base} (i.e., the case when $m+\left\vert E\right\vert =0$)
is trivial and left to the reader.

\textit{Induction step:} Let $N$ be a positive integer. Assume (as the
induction hypothesis) that Proposition \ref{prop.filtutte.pos} holds whenever
$m+\left\vert E\right\vert =N-1$. We need to show that Proposition
\ref{prop.filtutte.pos} holds whenever $m+\left\vert E\right\vert =N$.

So let us assume that we are in the situation of Proposition
\ref{prop.filtutte.pos}, and that we have $m+\left\vert E\right\vert =N$. We
need to show that%
\begin{equation}
T_{\mathbf{M}}\in\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2}%
,\ldots,y_{m}\right]  . \label{pf.prop.filtutte.pos.goal}%
\end{equation}


Since $\left(  M,\mathbf{E}\right)  $ is a filtered matroid, we have
$\varnothing=E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}=E$.

We have $m>0$\ \ \ \ \footnote{\textit{Proof.} We have $m+\left\vert
E\right\vert =N>0$. If we had $m=0$, then we would have $E_{m}=E_{0}$, which
would yield $\underbrace{m}_{=0}+\left\vert \underbrace{E}_{=E_{m}%
=E_{0}=\varnothing}\right\vert =\left\vert \varnothing\right\vert =0$, which
would contradict $m+\left\vert E\right\vert >0$. Hence, we cannot have $m=0$.
We thus have $m>0$, qed.}. Hence, $E_{m}\setminus E_{m-1}$ is well-defined. We
thus are in one of the following two cases:

\textit{Case 1:} We have $E_{m}\setminus E_{m-1}=\varnothing$.

\textit{Case 2:} We have $E_{m}\setminus E_{m-1}\neq\varnothing$.

Let us first consider Case 1. In this case, we have $E_{m}\setminus
E_{m-1}=\varnothing$. Combined with $E_{m-1}\subseteq E_{m}$ (since
$E_{0}\subseteq E_{1}\subseteq\cdots\subseteq E_{m}$), this entails that
$E_{m-1}=E_{m}$. Let $\mathbf{E}^{\prime}$ be the list $\left(  E_{0}%
,E_{1},\ldots,E_{m-1}\right)  $. Proposition \ref{prop.filtutte.m-1} thus
shows that $\left(  M,\mathbf{E}^{\prime}\right)  $ is a filtered matroid, and
satisfies $T_{\left(  M,\mathbf{E}\right)  }=T_{\left(  M,\mathbf{E}^{\prime
}\right)  }$. Now, $\left(  m-1\right)  +\left\vert E\right\vert
=\underbrace{m+\left\vert E\right\vert }_{=N}-1=N-1$. Hence, the induction
hypothesis shows that we can apply Proposition \ref{prop.filtutte.pos} to
$\left(  M,\mathbf{E}^{\prime}\right)  $, $\left(  E_{0},E_{1},\ldots
,E_{m-1}\right)  $ and $\mathbf{E}^{\prime}$ instead of $\mathbf{M}$, $\left(
E_{0},E_{1},\ldots,E_{m-1}\right)  $ and $\mathbf{E}$. As a consequence, we
conclude that $T_{\left(  M,\mathbf{E}^{\prime}\right)  }\in\mathbb{N}\left[
x_{1},x_{2},\ldots,x_{m-1},y_{1},y_{2},\ldots,y_{m-1}\right]  $. Now, from
$\mathbf{M}=\left(  M,\mathbf{E}\right)  $, we obtain%
\begin{align*}
T_{\mathbf{M}}  &  =T_{\left(  M,\mathbf{E}\right)  }=T_{\left(
M,\mathbf{E}^{\prime}\right)  }\in\mathbb{N}\left[  x_{1},x_{2},\ldots
,x_{m-1},y_{1},y_{2},\ldots,y_{m-1}\right] \\
&  \subseteq\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2}%
,\ldots,y_{m}\right]  .
\end{align*}
Thus, (\ref{pf.prop.filtutte.pos.goal}) is proven in Case 1.

Let us now consider Case 2. In this case, we have $E_{m}\setminus E_{m-1}%
\neq\varnothing$. Hence, there exists some $e\in E_{m}\setminus E_{m-1}$. Pick
such an $e$. Clearly, $e\in E_{m}\setminus E_{m-1}\subseteq E_{m}=E$.

The matroid $M\setminus e$ has ground set $E\setminus e$. The filtered matroid
$\mathbf{M}\setminus e=\left(  M\setminus e,\mathbf{E}\setminus e\right)  $
has $\mathbf{E}\setminus e=\left(  E_{0}\setminus e,E_{1}\setminus
e,\ldots,E_{m}\setminus e\right)  $. Now, $m+\underbrace{\left\vert E\setminus
e\right\vert }_{\substack{=\left\vert E\right\vert -1\\\text{(since }e\in
E\text{)}}}=\underbrace{m+\left\vert E\right\vert }_{=N}-1=N-1$. Hence, the
induction hypothesis shows that we can apply Proposition
\ref{prop.filtutte.pos} to $\mathbf{M}\setminus e$, $M\setminus e$,
$\mathbf{E}\setminus e$ and $\left(  E_{0}\setminus e,E_{1}\setminus
e,\ldots,E_{m}\setminus e\right)  $ instead of $\mathbf{M}$, $M$, $\mathbf{E}$
and $\left(  E_{0},E_{1},\ldots,E_{m}\right)  $. As a result, we obtain%
\[
T_{\mathbf{M}\setminus e}\in\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m}%
,y_{1},y_{2},\ldots,y_{m}\right]  .
\]

The matroid $M/e$ has ground set $E\setminus e$. The filtered matroid
$\mathbf{M}/e=\left(  M/e,\mathbf{E}\setminus e\right)  $ has $\mathbf{E}%
\setminus e=\left(  E_{0}\setminus e,E_{1}\setminus e,\ldots,E_{m}\setminus
e\right)  $. Now, recall that $m+\left\vert E\setminus e\right\vert =N-1$.
Hence, the induction hypothesis shows that we can apply Proposition
\ref{prop.filtutte.pos} to $\mathbf{M}/e$, $M/e$, $\mathbf{E}\setminus e$ and
$\left(  E_{0}\setminus e,E_{1}\setminus e,\ldots,E_{m}\setminus e\right)  $
instead of $\mathbf{M}$, $M$, $\mathbf{E}$ and $\left(  E_{0},E_{1}%
,\ldots,E_{m}\right)  $. As a result, we obtain%
\[
T_{\mathbf{M}/e}\in\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1}%
,y_{2},\ldots,y_{m}\right]  .
\]


We are in one of the following three subcases:

\textit{Subcase 2.1:} The element $e$ is a loop (of $M$).

\textit{Subcase 2.2:} The element $e$ is a coloop (of $M$).

\textit{Subcase 2.3:} The element $e$ is neither a loop nor a coloop.

Let us first consider Subcase 2.1. In this Subcase, the element $e$ is a loop
(of $M$). Hence, Proposition \ref{prop.filtutte.rec} \textbf{(a)} (applied to
$k=m$) yields%
\begin{align*}
T_{\mathbf{M}}  &  =y_{m}\underbrace{T_{\mathbf{M}\setminus e}}_{\in
\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots,y_{m}\right]
}\in y_{m}\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots
,y_{m}\right] \\
&  \subseteq\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2}%
,\ldots,y_{m}\right]  .
\end{align*}
Thus, (\ref{pf.prop.filtutte.pos.goal}) is proven in Subcase 2.1.

Let us now consider Subcase 2.2. In this Subcase, the element $e$ is a coloop
(of $M$). Hence, Proposition \ref{prop.filtutte.rec} \textbf{(b)} (applied to
$k=m$) yields%
\begin{align*}
T_{\mathbf{M}}  &  =x_{m}\underbrace{T_{\mathbf{M}/e}}_{\in\mathbb{N}\left[
x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots,y_{m}\right]  }\in x_{m}%
\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots,y_{m}\right] \\
&  \subseteq\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2}%
,\ldots,y_{m}\right]  .
\end{align*}
Thus, (\ref{pf.prop.filtutte.pos.goal}) is proven in Subcase 2.2.

Let us now consider Subcase 2.3. In this Subcase, the element $e$ is neither a
loop nor a coloop. Hence, Proposition \ref{prop.filtutte.rec} \textbf{(c)}
yields%
\begin{align*}
T_{\mathbf{M}}  &  =\underbrace{T_{\mathbf{M}\setminus e}}_{\in\mathbb{N}%
\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots,y_{m}\right]
}+\underbrace{T_{\mathbf{M}/e}}_{\in\mathbb{N}\left[  x_{1},x_{2},\ldots
,x_{m},y_{1},y_{2},\ldots,y_{m}\right]  }\\
&  \in\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2},\ldots
,y_{m}\right]  +\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2}%
,\ldots,y_{m}\right] \\
&  \subseteq\mathbb{N}\left[  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2}%
,\ldots,y_{m}\right]  .
\end{align*}
Thus, (\ref{pf.prop.filtutte.pos.goal}) is proven in Subcase 2.3.

We thus have proven (\ref{pf.prop.filtutte.pos.goal}) in each of the three
Subcases 2.1, 2.2 and 2.3. Since these three Subcases cover all of Case 2,
this yields that (\ref{pf.prop.filtutte.pos.goal}) always holds in Case 2.

We thus have proven (\ref{pf.prop.filtutte.pos.goal}) in each of the two Cases
1 and 2. Thus, (\ref{pf.prop.filtutte.pos.goal}) always holds. In other words,
Proposition \ref{prop.filtutte.pos} holds whenever $m+\left\vert E\right\vert
=N$. This completes the induction step. The inductive proof of Proposition
\ref{prop.filtutte.pos} is thus complete.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.filtutte.dual}.]Since $\left(  M,\mathbf{E}%
\right)  $ is a filtered matroid, we have $\varnothing=E_{0}\subseteq
E_{1}\subseteq\cdots\subseteq E_{m}=E$. Thus, $\left(  M^{\ast},\mathbf{E}%
\right)  $ is a filtered matroid (since $E$ is the ground set of $M^{\ast}$).
It remains to prove that $T_{\left(  M^{\ast},\mathbf{E}\right)
}=T_{\mathbf{M}}\left(  y_{1},y_{2},\ldots,y_{m},x_{1},x_{2},\ldots
,x_{m}\right)  $.

For every $S\in\mathcal{P}\left(  E\right)  $, let us write $\overline{S}$ for
the set $E\setminus S\in\mathcal{P}\left(  E\right)  $. We have%
\begin{equation}
n_{M^{\ast}}\left(  S\right)  =r_{M}\left(  E\right)  -r_{M}\left(
\overline{S}\right)  \ \ \ \ \ \ \ \ \ \ \text{for every }S\in\mathcal{P}%
\left(  E\right)  \label{pf.prop.filtutte.dual.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.filtutte.dual.1}):} Let
$S\in\mathcal{P}\left(  E\right)  $. The definition of $n_{M^{\ast}}$ yields%
\begin{align*}
n_{M^{\ast}}\left(  S\right)   &  =\left\vert S\right\vert
-\underbrace{r_{M^{\ast}}\left(  S\right)  }_{\substack{=\left\vert
S\right\vert +r_{M}\left(  E\setminus S\right)  -r_{M}\left(  E\right)
\\\text{(by (\ref{eq.def.dual-matroid.rank}))}}}=\left\vert S\right\vert
-\left(  \left\vert S\right\vert +r_{M}\left(  E\setminus S\right)
-r_{M}\left(  E\right)  \right)  \\
&  =r_{M}\left(  E\right)  -r_{M}\left(  \underbrace{E\setminus S}%
_{\substack{=\overline{S}\\\text{(since }\overline{S}=E\setminus S\text{)}%
}}\right)  =r_{M}\left(  E\right)  -r_{M}\left(  \overline{S}\right)  .
\end{align*}
This proves (\ref{pf.prop.filtutte.dual.1}).}. Furthermore,%
\begin{equation}
r_{M^{\ast}}\left(  S\right)  =n_{M}\left(  E\right)  -n_{M}\left(
\overline{S}\right)  \ \ \ \ \ \ \ \ \ \ \text{for every }S\in\mathcal{P}%
\left(  E\right)  \label{pf.prop.filtutte.dual.2}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.filtutte.dual.2}):} Let
$S\in\mathcal{P}\left(  E\right)  $. The definition of $n_{M}$ yields
$n_{M}\left(  E\right)  =\left\vert E\right\vert -r_{M}\left(  E\right)  $.
The definition of $n_{M}$ yields $n_{M}\left(  \overline{S}\right)
=\left\vert \overline{S}\right\vert -r_{M}\left(  \overline{S}\right)  $.
Since $S\subseteq E$, we have $\left\vert E\right\vert =\left\vert
S\right\vert +\left\vert E\setminus S\right\vert $, so that $\left\vert
S\right\vert =\left\vert E\right\vert -\left\vert \underbrace{E\setminus
S}_{\substack{=\overline{S}\\\text{(since }\overline{S}=E\setminus S\text{)}%
}}\right\vert =\left\vert E\right\vert -\left\vert \overline{S}\right\vert $.
Now,%
\begin{align*}
&  \underbrace{n_{M}\left(  E\right)  }_{=\left\vert E\right\vert
-r_{M}\left(  E\right)  }-\underbrace{n_{M}\left(  \overline{S}\right)
}_{=\left\vert \overline{S}\right\vert -r_{M}\left(  \overline{S}\right)  }\\
&  =\left(  \left\vert E\right\vert -r_{M}\left(  E\right)  \right)  -\left(
\left\vert \overline{S}\right\vert -r_{M}\left(  \overline{S}\right)  \right)
=\underbrace{\left\vert E\right\vert -\left\vert \overline{S}\right\vert
}_{=\left\vert S\right\vert }+r_{M}\left(  \underbrace{\overline{S}%
}_{=E\setminus S}\right)  -r_{M}\left(  E\right)  \\
&  =\left\vert S\right\vert +r_{M}\left(  E\setminus S\right)  -r_{M}\left(
E\right)  =r_{M^{\ast}}\left(  S\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{eq.def.dual-matroid.rank})}\right)  .
\end{align*}
This proves (\ref{pf.prop.filtutte.dual.2}).}.

The definition of $T_{\mathbf{M}}$ shows that
\[
T_{\mathbf{M}}=\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(
x_{i}-1\right)  ^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{n_{M}\left(  A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus
E_{i}\right)  }\right)  .
\]
Substituting $\left(  y_{1},y_{2},\ldots,y_{m},x_{1},x_{2},\ldots
,x_{m}\right)  $ for $\left(  x_{1},x_{2},\ldots,x_{m},y_{1},y_{2}%
,\ldots,y_{m}\right)  $ in this identity, we obtain%
\begin{align}
&  T_{\mathbf{M}}\left(  y_{1},y_{2},\ldots,y_{m},x_{1},x_{2},\ldots
,x_{m}\right) \nonumber\\
&  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{r_{M}\left(  A\cup E_{i}\right)  -r_{M}\left(  A\cup E_{i-1}\right)
}\right)  \left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)  ^{n_{M}\left(
A\setminus E_{i-1}\right)  -n_{M}\left(  A\setminus E_{i}\right)  }\right)
\nonumber\\
&  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(  y_{i}-1\right)
^{r_{M}\left(  \overline{A}\cup E_{i}\right)  -r_{M}\left(  \overline{A}\cup
E_{i-1}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)
^{n_{M}\left(  \overline{A}\setminus E_{i-1}\right)  -n_{M}\left(
\overline{A}\setminus E_{i}\right)  }\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }\overline{A}\text{ for }A\text{ in the sum,
since the map}\\
\mathcal{P}\left(  E\right)  \rightarrow\mathcal{P}\left(  E\right)
,\ A\mapsto\overline{A}\text{ is a bijection}%
\end{array}
\right) \nonumber\\
&  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)
^{n_{M}\left(  \overline{A}\setminus E_{i-1}\right)  -n_{M}\left(
\overline{A}\setminus E_{i}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(
y_{i}-1\right)  ^{r_{M}\left(  \overline{A}\cup E_{i}\right)  -r_{M}\left(
\overline{A}\cup E_{i-1}\right)  }\right)  . \label{pf.prop.filtutte.dual.A}%
\end{align}


On the other hand, every $i\in\left\{  1,2,\ldots,m\right\}  $ satisfies%
\begin{equation}
r_{M^{\ast}}\left(  A\cup E_{i}\right)  -r_{M^{\ast}}\left(  A\cup
E_{i-1}\right)  =n_{M}\left(  \overline{A}\setminus E_{i-1}\right)
-n_{M}\left(  \overline{A}\setminus E_{i}\right)
\label{pf.prop.filtutte.dual.3}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.filtutte.dual.3}):} Let $i\in\left\{
1,2,\ldots,m\right\}  $.
\par
We have $\overline{A\cup E_{i}}=E\setminus\left(  A\cup E_{i}\right)
=\underbrace{\left(  E\setminus A\right)  }_{=\overline{A}}\setminus
E_{i}=\overline{A}\setminus E_{i}$. Applying (\ref{pf.prop.filtutte.dual.2})
to $S=A\cup E_{i}$, we obtain%
\begin{equation}
r_{M^{\ast}}\left(  A\cup E_{i}\right)  =n_{M}\left(  E\right)  -n_{M}\left(
\underbrace{\overline{A\cup E_{i}}}_{=\overline{A}\setminus E_{i}}\right)
=n_{M}\left(  E\right)  -n_{M}\left(  \overline{A}\setminus E_{i}\right)  .
\label{pf.prop.filtutte.dual.3.pf.1}%
\end{equation}
The same argument (but applied to $E_{i-1}$ instead of $E_{i}$) yields%
\[
r_{M^{\ast}}\left(  A\cup E_{i-1}\right)  =n_{M}\left(  E\right)
-n_{M}\left(  \overline{A}\setminus E_{i-1}\right)  .
\]
Subtracting this equality from (\ref{pf.prop.filtutte.dual.3.pf.1}), we obtain%
\begin{align*}
&  r_{M^{\ast}}\left(  A\cup E_{i}\right)  -r_{M^{\ast}}\left(  A\cup
E_{i-1}\right) \\
&  =\left(  n_{M}\left(  E\right)  -n_{M}\left(  \overline{A}\setminus
E_{i}\right)  \right)  -\left(  n_{M}\left(  E\right)  -n_{M}\left(
\overline{A}\setminus E_{i-1}\right)  \right) \\
&  =n_{M}\left(  \overline{A}\setminus E_{i-1}\right)  -n_{M}\left(
\overline{A}\setminus E_{i}\right)  .
\end{align*}
This proves (\ref{pf.prop.filtutte.dual.3}).}. Furthermore, every
$i\in\left\{  1,2,\ldots,m\right\}  $ satisfies%
\begin{equation}
n_{M^{\ast}}\left(  A\setminus E_{i-1}\right)  -n_{M^{\ast}}\left(  A\setminus
E_{i}\right)  =r_{M}\left(  \overline{A}\cup E_{i}\right)  -r_{M}\left(
\overline{A}\cup E_{i-1}\right)  \label{pf.prop.filtutte.dual.4}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.filtutte.dual.4}):} Let $i\in\left\{
1,2,\ldots,m\right\}  $.
\par
We have $\overline{A\setminus E_{i}}=E\setminus\left(  A\setminus
E_{i}\right)  =\left(  E\setminus A\right)  \cup E_{i}$ (since $E_{i}\subseteq
E$), hence $\overline{A\setminus E_{i}}=\underbrace{\left(  E\setminus
A\right)  }_{=\overline{A}}\cup E_{i}=\overline{A}\cup E_{i}$. Applying
(\ref{pf.prop.filtutte.dual.1}) to $S=A\setminus E_{i}$, we obtain%
\begin{equation}
n_{M^{\ast}}\left(  A\setminus E_{i}\right)  =r_{M}\left(  E\right)
-r_{M}\left(  \underbrace{\overline{A\setminus E_{i}}}_{=\overline{A}\cup
E_{i}}\right)  =r_{M}\left(  E\right)  -r_{M}\left(  \overline{A}\cup
E_{i}\right)  . \label{pf.prop.filtutte.dual.4.pf.1}%
\end{equation}
The same argument (but applied to $E_{i-1}$ instead of $E_{i}$) yields%
\[
n_{M^{\ast}}\left(  A\setminus E_{i-1}\right)  =r_{M}\left(  E\right)
-r_{M}\left(  \overline{A}\cup E_{i-1}\right)  .
\]
Subtracting this equality from (\ref{pf.prop.filtutte.dual.4.pf.1}), we obtain%
\begin{align*}
&  n_{M^{\ast}}\left(  A\cup E_{i}\right)  -n_{M^{\ast}}\left(  A\cup
E_{i-1}\right) \\
&  =\left(  r_{M}\left(  E\right)  -r_{M}\left(  \overline{A}\setminus
E_{i}\right)  \right)  -\left(  r_{M}\left(  E\right)  -r_{M}\left(
\overline{A}\setminus E_{i-1}\right)  \right) \\
&  =r_{M}\left(  \overline{A}\setminus E_{i-1}\right)  -r_{M}\left(
\overline{A}\setminus E_{i}\right)  .
\end{align*}
This proves (\ref{pf.prop.filtutte.dual.4}).}. Now, recall that the matroid
$M^{\ast}$ has ground set $E$. Hence, the definition of $T_{\left(  M^{\ast
},\mathbf{E}\right)  }$ yields%
\begin{align*}
&  T_{\left(  M^{\ast},\mathbf{E}\right)  }\\
&  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\underbrace{\left(
x_{i}-1\right)  ^{r_{M^{\ast}}\left(  A\cup E_{i}\right)  -r_{M^{\ast}}\left(
A\cup E_{i-1}\right)  }}_{\substack{=\left(  x_{i}-1\right)  ^{n_{M}\left(
\overline{A}\setminus E_{i-1}\right)  -n_{M}\left(  \overline{A}\setminus
E_{i}\right)  }\\\text{(by (\ref{pf.prop.filtutte.dual.3}))}}}\right)  \left(
\prod_{i=1}^{m}\underbrace{\left(  y_{i}-1\right)  ^{n_{M^{\ast}}\left(
A\setminus E_{i-1}\right)  -n_{M^{\ast}}\left(  A\setminus E_{i}\right)  }%
}_{\substack{=\left(  y_{i}-1\right)  ^{r_{M}\left(  \overline{A}\cup
E_{i}\right)  -r_{M}\left(  \overline{A}\cup E_{i-1}\right)  }\\\text{(by
(\ref{pf.prop.filtutte.dual.3}))}}}\right) \\
&  =\sum_{A\subseteq E}\left(  \prod_{i=1}^{m}\left(  x_{i}-1\right)
^{n_{M}\left(  \overline{A}\setminus E_{i-1}\right)  -n_{M}\left(
\overline{A}\setminus E_{i}\right)  }\right)  \left(  \prod_{i=1}^{m}\left(
y_{i}-1\right)  ^{r_{M}\left(  \overline{A}\cup E_{i}\right)  -r_{M}\left(
\overline{A}\cup E_{i-1}\right)  }\right) \\
&  =T_{\mathbf{M}}\left(  y_{1},y_{2},\ldots,y_{m},x_{1},x_{2},\ldots
,x_{m}\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.prop.filtutte.dual.A})}\right)  .
\end{align*}
This proves Proposition \ref{prop.filtutte.dual}.
\end{proof}

As promised, we can now derive Proposition \ref{prop.tutte.rec} and Corollary
\ref{cor.tutte.positive}:

\begin{proof}
[Proof of Proposition \ref{prop.tutte.rec}.]Let $\mathbf{E}$ be the list
$\left(  \varnothing,E\right)  $. Then, Proposition \ref{prop.filtutte.m=1}
shows that $\left(  M,\mathbf{E}\right)  $ is a filtered matroid, and
satisfies $T_{\left(  M,\mathbf{E}\right)  }=T_{M}\left(  x_{1},y_{1}\right)
$. Clearly, $e\in E=E\setminus\varnothing$.

Let $\mathbf{M}$ be the filtered matroid $\left(  M,\mathbf{E}\right)  $.
Thus, $T_{\mathbf{M}}=T_{\left(  M,\mathbf{E}\right)  }=T_{M}\left(
x_{1},y_{1}\right)  $.

It is easy to see that $\mathbf{M}/e=\left(  M/e,\left(  \varnothing
,E\setminus e\right)  \right)  $. Write the matroid $M/e$ in the form $\left(
E\setminus e,\mathcal{J}\right)  $. Then, Proposition \ref{prop.filtutte.m=1}
(applied to $M/e$, $E\setminus e$ and $\mathcal{J}$ instead of $M$, $E$ and
$\mathcal{I}$) shows that $\left(  M/e,\left(  \varnothing,E\setminus
e\right)  \right)  $ is a filtered matroid, and satisfies $T_{M/e,\left(
\varnothing,E\setminus e\right)  }=T_{M/e}\left(  x_{1},y_{1}\right)  $. This
latter equality rewrites as $T_{\mathbf{M}/e}=T_{M/e}\left(  x_{1}%
,y_{1}\right)  $ (since $\mathbf{M}/e=\left(  M/e,\left(  \varnothing
,E\setminus e\right)  \right)  $).

It is easy to see that $\mathbf{M}\setminus e=\left(  M\setminus e,\left(
\varnothing,E\setminus e\right)  \right)  $. Write the matroid $M\setminus e$
in the form $\left(  E\setminus e,\mathcal{K}\right)  $. Then, Proposition
\ref{prop.filtutte.m=1} (applied to $M\setminus e$, $E\setminus e$ and
$\mathcal{K}$ instead of $M$, $E$ and $\mathcal{I}$) shows that $\left(
M\setminus e,\left(  \varnothing,E\setminus e\right)  \right)  $ is a filtered
matroid, and satisfies $T_{M\setminus e,\left(  \varnothing,E\setminus
e\right)  }=T_{M\setminus e}\left(  x_{1},y_{1}\right)  $. This latter
equality rewrites as $T_{\mathbf{M}\setminus e}=T_{M\setminus e}\left(
x_{1},y_{1}\right)  $ (since $\mathbf{M}\setminus e=\left(  M\setminus
e,\left(  \varnothing,E\setminus e\right)  \right)  $).

\textbf{(a)} Assume that $e$ is a loop. Proposition \ref{prop.filtutte.rec}
\textbf{(a)} (applied to $\left(  M,\mathbf{E}\right)  $, $\left(
\varnothing,E\right)  $ and $1$ instead of $\mathbf{M}$, $\left(  E_{0}%
,E_{1},\ldots,E_{m}\right)  $ and $k$) shows that $T_{\mathbf{M}}%
=y_{1}T_{\mathbf{M}\setminus e}$. Since $T_{\mathbf{M}}=T_{M}\left(
x_{1},y_{1}\right)  $ and $T_{\mathbf{M}\setminus e}=T_{M\setminus e}\left(
x_{1},y_{1}\right)  $, this rewrites as $T_{M}\left(  x_{1},y_{1}\right)
=y_{1}T_{M\setminus e}\left(  x_{1},y_{1}\right)  $. Substituting $x$ and $y$
for $x_{1}$ and $y_{1}$ in this equality, we obtain $T_{M}\left(  x,y\right)
=yT_{M\setminus e}\left(  x,y\right)  $. In other words, $T_{M}=yT_{M\setminus
e}$. This proves Proposition \ref{prop.tutte.rec} \textbf{(a)}.

\textbf{(b)} Assume that $e$ is a coloop. Proposition \ref{prop.filtutte.rec}
\textbf{(b)} (applied to $\left(  M,\mathbf{E}\right)  $, $\left(
\varnothing,E\right)  $ and $1$ instead of $\mathbf{M}$, $\left(  E_{0}%
,E_{1},\ldots,E_{m}\right)  $ and $k$) shows that $T_{\mathbf{M}}%
=x_{1}T_{\mathbf{M}/e}$. Since $T_{\mathbf{M}}=T_{M}\left(  x_{1}%
,y_{1}\right)  $ and $T_{\mathbf{M}/e}=T_{M/e}\left(  x_{1},y_{1}\right)  $,
this rewrites as $T_{M}\left(  x_{1},y_{1}\right)  =x_{1}T_{M/e}\left(
x_{1},y_{1}\right)  $. Substituting $x$ and $y$ for $x_{1}$ and $y_{1}$ in
this equality, we obtain $T_{M}\left(  x,y\right)  =xT_{M/e}\left(
x,y\right)  $. In other words, $T_{M}=xT_{M/e}$. This proves Proposition
\ref{prop.tutte.rec} \textbf{(a)}.

\textbf{(c)} Assume that $e$ is neither a loop nor a coloop. Proposition
\ref{prop.filtutte.rec} \textbf{(c)} (applied to $\left(  M,\mathbf{E}\right)
$ and $\left(  \varnothing,E\right)  $ instead of $\mathbf{M}$ and $\left(
E_{0},E_{1},\ldots,E_{m}\right)  $) shows that $T_{\mathbf{M}}=T_{\mathbf{M}%
\setminus e}+T_{\mathbf{M}/e}$. Since $T_{\mathbf{M}}=T_{M}\left(  x_{1}%
,y_{1}\right)  $, $T_{\mathbf{M}/e}=T_{M/e}\left(  x_{1},y_{1}\right)  $ and
$T_{\mathbf{M}\setminus e}=T_{M\setminus e}\left(  x_{1},y_{1}\right)  $, this
rewrites as $T_{M}\left(  x_{1},y_{1}\right)  =T_{M\setminus e}\left(
x_{1},y_{1}\right)  +T_{M/e}\left(  x_{1},y_{1}\right)  $. Substituting $x$
and $y$ for $x_{1}$ and $y_{1}$ in this equality, we obtain $T_{M}\left(
x,y\right)  =T_{M\setminus e}\left(  x,y\right)  +T_{M/e}\left(  x,y\right)
$. In other words, $T_{M}=T_{M\setminus e}+T_{M/e}$. This proves Proposition
\ref{prop.tutte.rec} \textbf{(c)}.
\end{proof}

\begin{proof}
[Proof of Corollary \ref{cor.tutte.positive}.]Let $\mathbf{E}$ be the list
$\left(  \varnothing,E\right)  $. Then, Proposition \ref{prop.filtutte.m=1}
shows that $\left(  M,\mathbf{E}\right)  $ is a filtered matroid, and
satisfies $T_{\left(  M,\mathbf{E}\right)  }=T_{M}\left(  x_{1},y_{1}\right)
$. Proposition \ref{prop.filtutte.pos} (applied to $\left(  M,\mathbf{E}%
\right)  $ and $\left(  \varnothing,E\right)  $ instead of $\mathbf{M}$ and
$\left(  E_{0},E_{1},\ldots,E_{m}\right)  $) shows that $T_{\left(
M,\mathbf{E}\right)  }\in\mathbb{N}\left[  x_{1},y_{1}\right]  $. Since
$T_{\left(  M,\mathbf{E}\right)  }=T_{M}\left(  x_{1},y_{1}\right)  $, this
rewrites as $T_{M}\left(  x_{1},y_{1}\right)  \in\mathbb{N}\left[  x_{1}%
,y_{1}\right]  $. Substituting $x$ and $y$ for $x_{1}$ and $y_{1}$ in this
relation, we obtain $T_{M}\left(  x,y\right)  \in\mathbb{N}\left[  x,y\right]
$. In other words, $T_{M}\in\mathbb{N}\left[  x,y\right]  $. This proves
Corollary \ref{cor.tutte.positive}.
\end{proof}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[LiPost15]{LiPost}Nan Li and Alexander Postnikov, \textit{Slicing
zonotopes}, ??

\bibitem[Martin15]{Martin15}%
\href{https://www.math.ku.edu/~jmartin/LectureNotes.pdf}{Jeremy L. Martin,
\textit{Lecture Notes on Algebraic Combinatorics}, August 19, 2015.}

\bibitem[Schrij13]{Schrij13}%
\href{http://homepages.cwi.nl/~lex/files/dict.pdf}{Alexander Schrijver,
\textit{A Course in Combinatorial Optimization}, February 3, 2013.}
\end{thebibliography}


\end{document}