\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\date{\dateline{April 4, 2014}{April 4, 2014}\\
\small Mathematics Subject Classifications: 05C63, 05C40, 05B35}


\usepackage{amsthm,amssymb,amsmath,enumerate,graphicx,psfrag}
%\usepackage[notref,notcite]{showkeys} % comment for final version
\usepackage{algorithm}




\newtheorem{definition}{Definition}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{corollary}[definition]{Corollary}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{conjecture}[definition]{Conjecture}
\newtheorem{question}[definition]{Question}
\newtheorem{problem}[definition]{Problem}
\newtheorem*{noCounterThm}{Theorem}
\newtheorem{algo}[definition]{Algorithm}

\newcommand{\kreis}[1]{\mathaccent"7017\relax #1}
\newcommand{\charf}[1]{\raisebox{\depth}{\(\chi\)}_{#1}}

\newcommand{\1}{{\rm 1\hspace*{-0.4ex}%
\rule{0.1ex}{1.52ex}\hspace*{0.2ex}}}


\newcommand{\comment}[1]{}
%\newcommand{\comment}[1]{\footnote{{\bf Comment:} #1}}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\es}{\emptyset}

\newcommand{\emtext}[1]{\text{\em #1}}

\newcommand{\mymargin}[1]{% 
  \marginpar{%
    \begin{minipage}{\marginparwidth}\small%
      \begin{flushleft}%
        #1%
      \end{flushleft}%
   \end{minipage}%
  }%
}%

\renewcommand{\mymargin}[1]{}%

% \begin{equation}\label{somelabel}
% \begin{minipage}[c]{0.8\textwidth}\em
% text goes in here
% \end{minipage}\ignorespacesafterend 
% \end{equation} 

\newcommand{\sm}{\setminus}
\newcommand{\mm}{-} % matroid minus as min M-X
\newcommand{\selfcite}[1]{$\!\!${\bf\cite{#1}}}

\newcommand{\del}{\ensuremath\text{\rm del}}
\newcommand{\ind}{\ensuremath\mathcal{I}}
%connectivity function
\newcommand{\cf}{\kappa}


\newcommand{\mfc}{\ensuremath{M_{\rm FC}}}% finite cycles
\newcommand{\mc}{\ensuremath{M_{\rm C}}}% topological cycles
\newcommand{\mfb}{\ensuremath{M_{\rm FB}}}% finite bonds
\newcommand{\mb}{\ensuremath{M_{\rm B}}}% bonds
\newcommand{\atc}{\ensuremath{M_{\rm AC}}}% algebraic cycles

\newcommand{\I}{\ensuremath\mathcal{I}}
\newcommand{\Imax}{\ensuremath\mathcal{I^{\rm max}}}

\newcommand{\eends}{\ensuremath\mathcal{E}} % edge-ends
\newcommand{\itop}[1]{||#1||} 


\title{Matroid and Tutte-connectivity  in infinite graphs}
%Matroid and Tutte-connectivity  in finitely separable graphs
%nur um das unendlich aus dem Titel zu haben?
\author{Henning Bruhn\\
\small Universit\"at Ulm, Germany\\
{\small\tt <henning.bruhn@uni-ulm.de>}}



%\date{}

\begin{document}
\maketitle

\begin{abstract}
We relate matroid connectivity to Tutte-connectivity in an infinite graph. 
Moreover, we show that the two cycle matroids, the finite-cycle matroid
and the cycle matroid, in which also infinite cycles are taken into account, 
have the same connectivity function. As an application we re-prove
that, also for infinite graphs, Tutte-connectivity is invariant under 
taking dual graphs.
\end{abstract}


\section{Introduction}

This work is part of a project to develop a theory for infinite
matroids that is analogous to its finite counterpart. 
In the initial paper of this project~\cite{infaxioms}, 
we extended  previous work of Higgs~\cite{Higgs69,Higgs69c} 
and Oxley~\cite{Oxley92}  by giving equivalent 
 definitions of (finite or infinite)
matroids in terms of independence, bases, circuits, closure and (relative) rank,
just as one is used to for finite matroids. 
Since then, in a series of papers~\cite{2sepmat,infintmat,matunion,matintbase,thindual}, 
several other aspects of infinite matroids have
been explored, among them graphic matroids~\cite{matgraphs}
and  matroid connectivity~\cite{linkingthm}.

These two last aspects are the focus of the current work: Connectivity in 
graphic matroids. For cycle matroids of finite graphs matroid connectivity
translates into a purely graph theoretic notion.
A graph  $G$ is \emph{$k$-Tutte-connected} if for every $\ell\leq k$ and every
partition $X,Y$ of its edge set into sets of at least $\ell$ edges each, 
the number of vertices incident with both an edge in $X$ and an edge in $Y$
is greater than~$\ell$. 
Tutte~\cite{tutte66} proved that a finite graph is $k$-Tutte-connected if and only if
its cycle matroid is $k$-connected.

The main result of this work is an extension of this fact to infinite graphs 
and matroids. For this, let us define the \emph{finite-cycle matroid} of any graph
by declaring to be independent any edge set 
that does not contain the edge set of a finite cycle. 

\begin{theorem}\label{mainthm}
Let $k\geq 2$ be an integer.
A graph is $k$-Tutte-connected if and only if its finite-cycle matroid
is $k$-connected.
\end{theorem}

If the graph in the theorem is infinite, the finite-cycle matroid clearly will be 
infinite as well. But what does it mean for an infinite matroid to be $k$-connected?
A finite matroid $M$ is $k$-connected if for any $\ell\leq k$ and any partition 
of its ground set into two sets $X,Y$ of at least $\ell$ elements each
it follows that
\(
r(X)+r(Y)-r(M)\geq \ell.
\)
Clearly, this definition is useless for infinite matroids as the involved
ranks will usually be infinite. In~\cite{linkingthm} we therefore gave 
a rank-free definition that carries over to infinite matroids. 
To argue that our definition is the right one, we showed that this notion
of connectivity has the same properties as in finite matroids and we,
furthermore, extended Tutte's linking theorem to at least a large subclass
of infinite matroids. Theorem~\ref{mainthm} substantiates our claim further. 

\medskip
Let us call a graph $G$ \emph{finitely separable}
if any two vertices may be separated by the deletion of finitely 
many edges.
In~\cite{matgraphs}, we observed that any {finitely separable}
graph has not one but two cycle matroids: the {finite-cycle matroid} 
and the \emph{cycle matroid}, in which any edge set containing 
a finite or infinite cycle is said to be dependent. Here, an infinite cycle 
in the graph is the homeomorphic image of the unit circle in a natural
topological space obtained from the graph (often by compactifying it). This definition
was proposed by Diestel and K\"uhn in a completely graph-theoretical context 
and was subsequently seen to be extremely fruitful as it allows to extend
virtually any result about cycles in a finite graph to at least 
a large class of infinite graphs; see Diestel~\cite{diestelBook10} for an introduction.  

The cycle matroid and the finite-cycle matroid coincide in a finite 
graph but will usually be different in infinite graphs. However, 
as we shall observe in Theorem~\ref{samecf}, they always have the same connectivity
and even the same connectivity function.


Finally, as an application of our argumentation, we get another 
extension of a result known for finite graphs: Tutte-connectivity 
is invariant under taking duals. 
\begin{theorem}$\!\!${\bf\cite{endduality}}\label{tconnthm}
Let $G$ and $G^*$ be a pair of dual graphs, and let $k\geq 2$.
Then $G$ is $k$-Tutte-connected if and only if $G^*$ is
$k$-Tutte-connected.
\end{theorem}
We remark that this is not a new result. In~\cite{endduality}
we gave a graph-theoretical proof. Here, we will see a matroidal variant.




\section{Infinite cycles}

Let us fix a finitely separable graph $G=(V,E)$ in this section.

A \emph{ray} of $G$ is a one-way infinite path. Two rays are \emph{edge-equivalent} if
for every finite set of edges $F$ there is a component of $G-F$ that contains
subrays of both rays. The equivalence classes of this relation are the 
\emph{edge-ends $\eends(G)$} of~$G$.

We view the edges of $G$ as disjoint homeomorphic images of the unit interval $[0,1]$, 
and define the quotient space $X_G$ by identifying these copies of $[0,1]$
at their common endvertices. Let us define a topological space $\itop G$ on 
$X_G\cup\eends(G)$ by specifying the basic open sets: these are all sets
of the form $\tilde C$, which consists of a topological component of $X_G-Z$
for some finite set $Z$ of inner points of edges together with all edge-ends
that have a ray lying entirely in $C$. We remark that normally this space will 
not be Hausdorff: no edge-end can be separated from a vertex that sends 
infinitely many edge-disjoint paths to one of its rays. However, 
and this is the reason for imposing finite separability, 
two vertices may always be topologically distinguished.
For a locally finite $G$, that is, a graph in which every vertex has finite degree, 
the space $\itop G$ coincides with the Freudenthal compactification.

\medskip

For us a \emph{cycle of $\itop G$} is  
 a homeomorphic image of the unit circle $S^1$ in $\itop G$. This definition of cycles
includes the traditional finite cycles but allows also other cycles, which then 
contain necessarily infinitely many vertices and edges. 
A \emph{standard subspace} of $\itop G$ is the closure of a subgraph of $G$ in $\itop G$.
The set of edges that are completely contained in a standard subspace $X$
are denoted by $E(X)$.
Cycles are standard 
subspaces~\cite{Moritz}.  
A \emph{topological spanning tree} of $\itop G$ is a standard subspace that is path-connected in $\itop G$
and which contains every vertex of $G$ but no cycle. For more details see~\cite{matgraphs}.

\begin{figure}[ht]
\centering
\includegraphics[scale=1]{infcycle}
\caption{An infinite cycle in the double ladder}\label{dladder}
\end{figure}

In Figure~\ref{dladder} some of the introduced concepts are illustrated. The graph there, the double 
ladder, has two edge-ends, one to the left and one to the right. The infinite cycle $C$ in bold lines 
goes through these two edge-ends. 
Moreover, while $C+f$ is a spanning tree of the graph it is not
(even including the two edge-ends) a topological spanning tree, simply because it contains
the infinite cycle $C$. On the other hand, $C-e$ can be seen to be one. Its connectivity
is ensured by the edge-ends. 

\section{Infinite matroids}


As finite matroids,
infinite matroids come with a number of different axiom systems. We only describe here the
\emph{independence axioms}. Let $E$ be a set, let $\I\subseteq 2^E$ be a set of subsets of $E$,
and denote by $\Imax$ the sets in $\I$ that are maximal under inclusion.
We say that $M=(E,\I)$ is a \emph{matroid} with independent sets $\I$ if 
the following axioms are satisfied:
\begin{itemize}
\item[\rm (I1)] $\emptyset\in\mathcal I$.
\item[\rm (I2)] $\I$ is closed under taking subsets, 
that is if $I\in\I$ and $J\subseteq I$ then $J\in \I$.
\item[\rm (I3)] For all $I\in\I\sm\Imax$ and $I'\in\Imax$ there is an $x\in I'\sm I$ such that $I\cup\{x\}\in\I$
\item[\rm (IM)] The set 
$\{\,I'\in\I: I\subseteq I'\subseteq X\,\}$ has a maximal element, 
whenever $I\subseteq X\subseteq E$ and $I\in\I$.
\end{itemize}
Infinite matroids show the same properties as finite matroids. In particular, 
they possess bases ($\subseteq$-maximal independent sets), 
circuits (minimal dependent sets) and a natural notion of duality, in much of the same
way as finite matroids,  see~\cite{infaxioms}. 
In particular, $B\subseteq E$ is a base of $M$ if and only if $E\sm B$ 
is a base of the dual matroid $M^*$. 
We will use the normal matroid 
terminology. For instance, for any subset $X$ of the ground set $E$
of a matroid $M$ we will write $M|X$ for the restriction of $M$ to $X$, and 
we write $M\mm X=M|(E\sm X)$ for the matroid obtained by deleting the elements in $X$
from $M$.



In~\cite{linkingthm}, the \emph{connectivity function} $\cf$  
is extended to infinite matroids. For any $X\subseteq E(M)$ in a matroid $M$,
choose a base $B$ of $M|X$ and a base $B'$ of $M\mm X$, and pick a 
set $F\subseteq B\cup B'$ so that $(B\cup B')\sm F$ is a base of $M$.
Then we set 
$\cf_M(X):=|F|\in\mathbb N\cup\{\infty\}$ (we do not distinguish between
different infinite cardinalities). 
We remark that the value $\cf_M(X)$ is independent of the choice of the bases
and of the choice of $F$. Moreover, 
$F$ may be chosen to be a subset of $B$ or of $B'$, if necessary.
This definition of the connectivity function has similar properties 
as the traditional connectivity function of a finite matroid. 
For finite matroids, the two notions coincide. More details and  proof
that $\cf$ is well-defined can be found in~\cite{linkingthm}.

We call
a partition $(X,Y)$ of $E$ a \emph{$\ell$-separation} if 
$\cf_M(X)\leq \ell-1$ and $|X|,|Y|\geq \ell$.
The matroid $M$ is \emph{$k$-connected} if there exists no $\ell$-separation
with $\ell<k$.


\medskip

Infinite graphs are a natural source of infinite matroids. 
Two dual matroids are normally associated with a finite graph,
the cycle matroid and the bond matroid. These matroids can be extended
verbatim to an infinite graph $G=(V,E)$.
Let $\I$ be the set
of all edge sets $I\subseteq E$ not containing the edge set
of any finite cycle of $G$. Then $\I$ is the set of independent 
sets of a matroid $\mfc(G)$, the \emph{finite-cycle matroid of $G$}. 
Its circuits are precisely the edge sets of finite cycles, and its bases
coincide with the \emph{spanning forests}, the sets that form a spanning tree 
on every component. In a similar fashion, we may now define
a matroid whose circuits are the finite bonds, the \emph{finite-bond matroid $\mfb(G)$}. 
However, $\mfc(G)$ and $\mfb(G)$ are no longer dual. If $G$ 
is finitely separable, then
the dual of $\mfb(G)$ is the \emph{cycle matroid $\mc(G)$}, 
whose circuits are precisely the edge sets of (finite or infinite) cycles of $\itop{G}$.
If $G$ is connected then the bases of $\mc(G)$ are the edge sets of topological spanning
trees of $\itop{G}$ and vice versa; see~\cite{matgraphs}.

\medskip

If the graph $G$ is infinite and $2$-connected then the two matroids $\mfc(G)$ and $\mc(G)$ will 
differ. As an illustration, consider again the double ladder in Figure~\ref{dladder}. The 
set of edges in bold will be independent in $\mfc(G)$ but not in $\mc(G)$.

\section{Matroid connectivity in infinite graphs}\label{sec:graphconn}




In a graph $G$, denote for $X\subseteq E(G)$
by $V[X]$ the set of
vertices that are incident with an edge in $X$.
Let $c(X)$
be the number of components of the subgraph~$(V[X],X)$ of $G$.

Our first aim is the following theorem:

\begin{theorem}
\label{mat:matconn}
Let $G$ be a $2$-connected graph, and let
$X\subseteq E(G)$, and  $Y:=E(G)\sm X$.
Then the following statements hold:
\begin{enumerate}[\rm (i)]
\item $\cf_{\mfc(G)}(X)=\infty$ if and only if $|V[X]\cap V[Y]|=\infty$; and
\item if $\cf_{\mfc(G)}(X)<\infty$ then 
\[
\cf_{\mfc(G)}(X)=|V[X]\cap V[Y]|-c(X)-c(Y)+1.
\]
\end{enumerate}
\end{theorem}
Statement~(ii) is exactly as for finite graphs when the traditional connectivity
function is used, see Tutte~\cite{tutte66}. 

\begin{proof}[Proof of Theorem~\ref{mat:matconn}]
(i) 
We first consider the case when $|V[X]\cap V[Y]|=\infty$.
Starting with a cycle $G_1$ that intersects both $X$ and $Y$, we inductively
construct connected subgraphs $G_n$ of $G$ as follows. Pick 
two edges $e\in X$ and $f\in Y$ with a common endvertex $v$ that lies in 
$(V[X]\cap V[Y])\sm V(G_n)$. 
Observe that,
as $G$ is $2$-connected,
 there is a (finite) cycle passing through $e$ and $f$. 
If the cycle meets $G_n$ in at most one vertex, we set $P_{n+1}$ to be the cycle
together with a shortest path from the cycle to $G_n$ (equal to the single common
vertex between the cycle and $G_n$ if there is such a vertex). 
If the cycle meets $G_n$ in at least two vertices, there is a path $P_{n+1}$
through $e$ and $f$ whose endvertices are in $G_n$ but for which none of the 
internal vertices are contained in $G_n$. In both cases, $G_{n+1}:=G_n\cup P_{n+1}$
is connected and, as can be seen inductively,   neither $E(G_{n+1})\cap X$
nor $E(G_{n+1})\cap Y$ contains a (finite) cycle. 
Moreover, if $F$ is a set of 
edges so that $G_{n+1}-F$ is devoid of cycles then $|F|\geq n+1$:
suppose there is such a set $F$ of cardinality at most $n$. Then 
$F\subseteq E(G_n)$ as, by induction, already $n$ edges are needed
to meet every cycle of $G_n$. In fact, since $G_n$ is connected, 
the graph $G_n-F$ is a tree. In particular, $P_{n+1}$ cannot contain a cycle.
Therefore, $P_{n+1}$ is a path with its two endvertices in $G_n$ that is internally
disjoint from $G_n$. The two endvertices of $P_{n+1}$
in $G_n$ are connected by a path $Q$ in $G_n-F$. But then $P_{n+1}\cup Q$
is a cycle in $G_{n+1}-F$, which is impossible.

Now, $\bigcup_{n=1}^\infty E(G_n)\cap X$ does not contain any circuit
of $\mfc(G)$. Thus, we may extend this independent set to a base $B_X$
of $\mfc(G)|X$, and we define $B_Y$ analogously. Consider a set $F\subseteq B_X\cup B_Y$
so that $(B_X\cup B_Y)\sm F$ is a base of $\mfc(G)$, and suppose that 
$F$ has finite cardinality $n$. However, by construction,
$G_{n+1}-F$ still contains at least 
one cycle, in contradiction to $E(G_{n+1})\subseteq B_X\cup B_Y$.
Therefore, $|F|=\infty$, which means that $\cf_{\mfc(G)}(X)=\infty$.


\medskip
Secondly, we treat the case when
$|V[X]\cap V[Y]|<\infty$. Pick a base $T_X$ 
 of $\mfc(G)|X$, and let $T_Y$
be a base of $\mfc(G)|Y$. Then $T_X$ is (the edge set of) a spanning tree on every component
of $(V[X],X)$,
and $T_Y$ is such 
a maximal spanning forest of $(V[Y],Y)$. Thus, for any pair $u,v$ of vertices
in $V[X]\cap V[Y]$ there is at most one path $P_{uv}$ in $T_X$ from $u$ to $v$. 
Let $F$ be a set of edges that chooses one edge from each $P_{uv}$,
where $u,v$ are distinct vertices in $V[X]\cap V[Y]$. 
Note that $F$ is a finite set
as there are only finitely many pairs $u,v$. Moreover, $(T_X\cup T_Y)\sm F$
contains no finite  cycle of $G$ and is therefore independent in $\mfc(G)$.
As $|F|$ is  an upper bound for $\cf_{\mfc(G)}(X)$ the 
result follows. 

\medskip
(ii) 
Pick a spanning tree on every component of $(V[X],X)$ and denote 
the union of their edge sets by $T_X$. We define $T_Y$ for $(V[Y],Y)$
in a similar way. Choose a set of edges $F\subseteq X$ so that $T:=(T_X\cup T_Y)\sm F$
is a base of $\mfc(G)$, i.e.\ the edge set of a spanning tree of $G$.

We claim that
\begin{equation}
\label{ma:eq:onecomp}
\emtext{if $c(X)=c(Y)=1$ then $\cf_{\mfc(G)}(X,Y)=|V[X]\cap V[Y]|-1$.}
\end{equation}
Let us prove the claim. Each vertex in $U:=V[X]\cap V[Y]$ must lie
in a distinct component of $(V[T_X],T_X\sm F)$ since otherwise there exists a
path in $(V[T_X],T_X\sm F)$ that starts and ends in $U$ but is otherwise disjoint from $U$.
This path can be extended with edges in $T_Y$
to a finite cycle that still misses $F$, which is impossible as $(T_X\cup T_Y)\sm F$ is the edge set of a tree. 
As $(V[T_X],T_X)$ is connected
and as each deletion of a single edge increases the number of components
by exactly one, we obtain $|F|\geq |U|-1$. 
Suppose, on the other hand, that $|F|> |U|-1$. Then there exists a
component $K$ of $(V[T_X],T_X\sm F)$ that contains no vertex of $U$,
which means that $K$ is a component of $(V(G),T)$.
However, as $G$ is connected the base $T$ of $\mfc(G)$ is the edge set 
of a spanning tree. This contradiction  
proves~\eqref{ma:eq:onecomp}.
 

We now proceed by induction on $c(X)+c(Y)$, which is indeed a finite
number as $|V[X]\cap V[Y]|$ is an upper bound for both $c(X)$ and $c(Y)$.
Since the induction start is established by~\eqref{ma:eq:onecomp},
we may assume that $(V[X],X)$ has two components $K$ and $K'$. 
Insert a new edge $f$ between $K$ and $K'$, and set $G':=G+f$
and $X':=X\cup\{f\}$. Clearly, $(X',Y)$ is a partition of $E(G')$.
Since $c(X')=c(X)-1$, the induction yields
\[
\cf_{\mfc(G')}(X',Y)
=|V[X]\cap V[Y]|-(c(X)-1)-c(Y)+1.
\]

We shall now show that $\cf_{\mfc(G')}(X',Y)=\cf_{\mfc(G)}(X,Y)+1$. 
Observe that then $T_X+f$ is (the edge set of)
a maximal spanning forest of $(V[X'],X')\subseteq G'$. Moreover,
$(T_X\sm F)\cup T_Y=((T_X+f)\sm (F\cup\{f\}))\cup T_Y$ is a spanning
tree of $G'$, too. Thus
\[
\cf_{\mfc(G')}(X,Y')=|F\cup\{f\}|=|F|+1=\cf_{\mfc(G)}(X,Y)+1,
\]
which finishes the proof.
\end{proof}



Next, let us show that the connectivity functions of $\mfc(G)$
and $\mc(G)$ coincide. For this, we need two results, one on spanning 
trees and one on the connectivity function under duality.

\begin{theorem}\selfcite{duality}\label{acircST}
Every connected finitely separable graph $G$ has a spanning tree
whose closure in $\itop{G}$ is a topological spanning tree of $\itop{G}$.
\end{theorem}

\begin{lemma}\selfcite{linkingthm}\label{kapduallem}
The connectivity function is invariant under duality, that is, 
$\cf_M(X)=\cf_{M^*}(X)$ for any subset $X$ of a matroid $M$.
\end{lemma}


\begin{theorem}\label{samecf}
Let $G$ be a connected finitely separable graph. Then
\[
\cf_{\mc(G)}(X)=\cf_{\mfc(G)}(X)
\] 
for all $X\subseteq E(G)$.
\end{theorem}
\begin{proof}
Let $B$ be 
the edge set of a spanning tree as in Theorem~\ref{acircST}.
As then $B$ is as well the edge set of a topological spanning tree, 
we see that $B$ is simultaneously a base of $\mfc(G)$ and of $\mc(G)$.

We use (IM) to extend $B\cap X$ to a base $B_X$ of $\mc(G)|X$.
Since $B_X$ is independent in $\mfc(G)$ (but not necessarily a base)
we may extend $B_X$ to a base $B'_X$ of $\mfc(G)|X$. Analogously, 
we define a base $B_{\overline X}\supseteq B\sm X$ of $\mc(G)\mm X$,
and a base $B'_{\overline X}\supseteq B_{\overline X}$ of  $\mfc(G)\mm X$.
Therefore, setting
$F':=(B'_X\cup B'_{\overline X})\sm B$, we obtain $\cf_{\mfc(G)}(X)=|F'|$. 
In a similar way,  $\cf_{\mfc(G)}(X)=|F|$ for $F=(B_X\cup B_{\overline X})\sm B$.
As $F\subseteq F'$, we deduce 
\[
\cf_{\mc(G)}(X)\leq \cf_{\mfc(G)}(X).
\]

Next, we observe that $E(G)\sm B$ is a base of $\mc^*(G)$ as well as of $\mfc^*(G)$.
Since any independent set in $\mfc^*(G)$ is also independent in $\mc^*(G)$,
we may use the same arguments as above to deduce that 
\(
\cf_{\mfc^*(G)}(X)\leq \cf_{\mc^*(G)}(X).
\)
Finally, the invariance of the connectivity function under duality
(Lemma~\ref{kapduallem}) yields 
$\cf_{\mfc(G)}(X)=\cf_{\mc(G)}(X)$.
\end{proof}

In particular, we have the following consequence:
\begin{corollary}\label{sameconn}
Let $G$ be a connected finitely separable graph, and let $k\geq 2$. 
Then $\mfc(G)$ is $k$-connected if and only if $\mc(G)$ is $k$-connected.
\end{corollary}

\section{Proof of main result}

Let us recall the definition of Tutte-connectivity.
A \emph{$\ell$-Tutte-separation} of a graph $G$ is a partition $(X,Y)$ of 
$E(G)$ so that $|X|,|Y|\geq \ell$ and so that $|V[X]\cap V[Y]|\leq \ell$.
We say that a graph $G$ is \emph{$k$-Tutte-connected} 
if $G$ has no $\ell$-Tutte-separation for any $\ell<k$.

\begin{proof}[Proof of Theorem~\ref{mainthm}]
As matroid connectivity and Tutte-connectivity are
only concerned with edge sets, we may assume that $G$ has no 
isolated vertices. Moreover, $G$ can be required to be $2$-connected:
otherwise each cut-vertex (or component) gives rise to a $1$-Tutte-separation
as well as to a $1$-separation. Finally, we assume $G$ to be an 
infinite graph: for finite graphs, 
see Tutte~\cite{tutte66}---note that
$\mfc(G)$ and $\mc(G)$ coincide in this case.
We  need to 
prove that $G$ has a $k$-Tutte-separation with $k\leq m$
if and only if $\mfc(G)$ has an $\ell$-separation
with $\ell\leq m$.



First, let $(X,Y)$ be a $k$-Tutte-separation $(X,Y)$ of $G$,
which implies $|V[X]\cap V[Y]|\leq k$.
Since $c(X),c(Y)\geq 1$ this yields with Theorem~\ref{mat:matconn}
that $\cf_{\mfc(G)}\leq k-1$. Consequently, $(X,Y)$
is a $k$-separation of $\mfc(G)$.

Conversely, let there be an $\ell$-separation in $\mfc(G)$, and choose an
$\ell$-separation $(X,Y)$ of $\mfc(G)$ so that
$c(X)+c(Y)$ is minimal among all $\ell$-separations of $\mfc(G)$.
Note that, by Theorem~\ref{mat:matconn}, for any $\ell$-separation $(X,Y)$
the sum $c(X)+c(Y)$ is finite.
Since $G$ is infinite, we may assume that $Y$ is an infinite
set.

First, we claim that 
\begin{equation}
\label{Y:conn}
\emtext{$(V[Y],Y)$ is connected}.
\end{equation}
If $(V[Y],Y)$ is not connected then there is a component $K$ of $(V[Y],Y)$
so that $Y':=Y\sm E(K)$ is an infinite set. With $X':=X\cup E(K)$ we
see that both $X'$ and $Y'$ have at least $\ell$ elements. Moreover, it holds that
$|V[X]\cap V[Y]|= |V[X']\cap V[Y']| + |V[X]\cap V[K]|$ and $c(Y)=c(Y')+1$.
The set of  components of $(V[X'],X')$ is comprised of those components of $(V[X],X)$
that are disjoint from $K$ together with the 
union of $K$ and those components of $(V[X],X)$ that have a vertex with $K$ 
in common. Since there are at most $|V[X]\cap V[K]|$
components of the latter kind, we obtain $c(X)\leq c(X')+|V[X]\cap V[K]|-1$.
It follows with Theorem~\ref{mat:matconn} that
\begin{eqnarray*}
\cf_{\mfc(G)}(X',Y')& =&|V[X']\cap V[Y']|-c(X')-c(Y')+1\\
&\leq & |V[X]\cap V[Y]| -|V[X]\cap V[K]|-c(X)\\
&&+\,|V[X]\cap V[K]|-1-c(Y)+1+1\\
&=& |V[X]\cap V[Y]|-c(X)-c(Y)+1\leq \ell-1.
\end{eqnarray*}
Thus, $(X',Y')$ is an $\ell$-separation with $c(X')+c(Y')< c(X)+c(Y)$,
contradicting the choice of $(X,Y)$.

Secondly, we show that
\begin{equation}
\label{Xcomps}
\emtext{$|V[K]\cap V[Y]|\leq \ell$ for every component $K$ of $(V[X],X)$.}
\end{equation}
Suppose there exists a component $M$ of $(V[X],X)$ with $|V[M)]\cap V[Y]|\geq \ell+1$.
Denoting by $\mathcal K$ the components of $(V[X],X)$ we get
\begin{eqnarray*}
\ell-1&\geq & |V[X]\cap V[Y]|-c(X)-c(Y)+1\\
&\geq&\sum_{K\in\mathcal K\sm\{M\}} |V[K]\cap V[Y]| + (\ell+1) -c(X)-c(Y)+1.
\end{eqnarray*}
That $G$ is connected implies $|V[K]\cap V[Y]|\geq 1$ for every $K\in\mathcal K$.
Hence
\[
\ell-1\geq  (c(X)-1) + (\ell+1) -c(X)-c(Y)+1 = \ell+1-c(Y).
\]
This yields $c(Y)\geq 2$, which is impossible by~\eqref{Y:conn}.
Therefore,~\eqref{Xcomps} is proved.

Next, we see that
\begin{equation}
\label{goodcomp}
\emtext{there is a  component $M$ of $(V[X],X)$ with $|E(M)|\geq |V[M]\cap V[Y]|$.}
\end{equation}
If~\eqref{goodcomp} is false then we have $|V[K]\cap V[Y]|\geq |E(K)|+1$ for all $K\in\mathcal K$.
This, however, implies with $c(Y)=1$ that
\begin{eqnarray*}
\ell-1&\geq & |V[X]\cap V[Y]|-c(X)-c(Y)+1\\
&=&\sum_{K\in\mathcal K} |V[K]\cap V[Y]|  -c(X)\\
&\geq&\sum_{K\in\mathcal K} (|E(K)|+1)  -c(X) \,=\, |X|.
\end{eqnarray*}
As $(X,Y)$ is an $\ell$-separation, $X$ is required to have at least $\ell$ elements,
which shows that~\eqref{goodcomp} holds.

Finally, with the component $M$ from~\eqref{goodcomp} we set $\bar X:=E(M)$
and $\bar Y:=E(G)\sm E(M)$. Then $k:=|V[\bar X]\cap V[\bar Y]|=|V[M]\cap V[Y]|\leq \ell$,
by~\eqref{Xcomps}. As $|\bar X|\geq k$ and $|\bar Y|=\infty$ it follows
that $(\bar X,\bar Y)$ is a $k$-Tutte-separation with $k\leq \ell$, as
desired.
\end{proof}
We remark that the arguments in the proof are not new.
Indeed,~\eqref{Y:conn} is inspired by Tutte~\cite{tutte66} and 
steps~\eqref{Xcomps},~\eqref{goodcomp} are quite similar to the proof of 
Lemma~5.3 in~\cite{endduality}.



\section{Tutte-connectivity and duality}

In this final section, we deduce a matroidal proof of the fact that
Tutte-connectivity is invariant under duality (Theorem~\ref{tconnthm}). 

Two finitely separable countable graphs $G$ and $G^*$ 
defined on the same edge set $E$
are a pair 
of \emph{duals} if  any edge set $F\subseteq E$ is the edge set of
a cycle of $\itop G$
if and only if $F$ is a bond of $G^*$.
(A \emph{bond} is a minimal non-empty cut.)
As for finite graphs, a (countable) finitely separable graph is planar
if and only if it has a dual, see~\cite{duality} for a proof and more details.


We need a result on how graph duality relates to matroid duality:


\begin{theorem}\selfcite{matgraphs}
\label{graphdual}
Let $G$ and $G^*$ be a pair of countable  dual graphs, each finitely separable, and defined on the same edge set~$E$. Then 
\(
\mc^*(G)=\mfc(G^*).
\)
\end{theorem}

Consider a pair of countable dual graphs $G$ and $G^*$.
Then, by Theorem~\ref{mainthm},
 $G$ is $k$-Tutte-connected if and only if $\mfc(G)$
is $k$-connected. Since $\mfc(G)=(\mc(G^*))^*$ by Theorem~\ref{graphdual}
and since matroid connectivity is invariant under taking duals 
(Lemma~\ref{kapduallem})
this is precisely the case when $\mc(G^*)$ is $k$-connected. 
Finally, Theorem~\ref{mainthm} in conjunction with Corollary~\ref{sameconn}
shows that 
$\mc(G^*)$ is $k$-connected if and only if $G^*$ is $k$-Tutte-connected.
This proves Theorem~\ref{tconnthm}.

\subsection*{Acknowledgement}

I am grateful to the referee who suggested that the condition of being finitely
separable could be dropped from Theorem~\ref{mainthm} and I thank the referee
who caught the small error in the proof of Theorem~\ref{mat:matconn}.


\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{thindual}
H.~Afzali and N.~Bowler, \emph{Thin sums matroids and duality}, Preprint 2012.

\bibitem{matunion}
E.~Aigner-Horev, J.~Carmesin, and J.~Fr{\"o}hlich, \emph{Infinite matroid
  union}, Preprint 2012.

\bibitem{2sepmat}
E.~Aigner-Horev, R.~Diestel, and L.~Postle, \emph{The structure of
  2-separations of infinite matroids}, Preprint 2012.

\bibitem{matintbase}
N.~Bowler and J.~Carmesin, \emph{Matroid intersection, base packing and base
  covering for infinite matroids}, Preprint 2012.

\bibitem{infintmat}
\bysame, \emph{Matroids with an infinite circuit-cocircuit intersection},
  Preprint 2012.

\bibitem{duality}
H.~Bruhn and R.~Diestel, \emph{Duality in infinite graphs}, Comb.,\ Probab.\
  Comput. \textbf{15} (2006), 75--90.

\bibitem{matgraphs}
\bysame, \emph{Infinite matroids in graphs}, Disc.\ Math. \textbf{311} (2011),
  1461--1471.

\bibitem{infaxioms}
H.~Bruhn, R.~Diestel, M.~Kriesell, R.~Pendavingh, and P.~Wollan, \emph{Axioms
  for infinite matroids}, Advances in Mathematics \textbf{239} (2013), 18--46.

\bibitem{endduality}
H.~Bruhn and M.~Stein, \emph{Duality of ends}, Comb.,\ Probab.\ Comput.
  \textbf{19} (2010), 47--60.

\bibitem{linkingthm}
H.~Bruhn and P.~Wollan, \emph{Finite connectivity in infinite matroids},
  Europ.\ J.\ Comb. \textbf{33} (2012), 1900--1912.

\bibitem{diestelBook10}
R.~Diestel, \emph{Graph theory \emph{(4th edition)}}, Springer-Verlag, 2010.

\bibitem{Higgs69c}
D.A. Higgs, \emph{Infinite graphs and matroids}, Recent Prog.\ Comb., Proc.\
  3rd Waterloo Conf., 1969, pp.~245--253.

\bibitem{Higgs69}
\bysame, \emph{Matroids and duality}, Colloq.\ Math. \textbf{20} (1969),
  215--220.

\bibitem{Oxley92}
J.G. Oxley, \emph{Infinite matroids}, Matroid applications (N.~White, ed.),
  Encycl.\ Math.\ Appl., vol.~40, Cambridge University Press, 1992, pp.~73--90.

\bibitem{Moritz}
M.~Schulz, \emph{Der {Z}yklenraum nicht lokal-endlicher {G}raphen}, Diploma
  thesis, Universit{\"a}t {H}amburg (2005).

\bibitem{tutte66}
W.T. Tutte, \emph{Connectivity in matroids}, Can.\ J.\ Math. \textbf{18}
  (1966), 1301--1324.

\end{thebibliography}



\end{document} 

%%%%%%%%%%%%%%%%% end of doc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[ht]
\centering
\includegraphics[scale=1]{}
\caption{}\label{}
\end{figure}

\begin{equation}\label{somelabel}
\begin{minipage}[c]{0.8\textwidth}\em
text goes in here
\end{minipage}\ignorespacesafterend 
\end{equation} 


