# The Lovász-Cherkassky theorem in infinite graphs

Attila Joó  Attila Joó, Department of Mathematics, University of Hamburg,
Bundesstraße 55 (Geomatikum), 20146 Hamburg, Germany  attila.joo@uni-
hamburg.de

###### Abstract.

Infinite generalizations of theorems in finite combinatorics were initiated by
Erdős due to his famous Erdős-Menger conjecture (now known as the Aharoni-
Berger theorem) that extends Menger’s theorem to infinite graphs in a
structural way. We prove a generalization of this manner of the classical
result about packing edge-disjoint $T$-paths in an “inner Eulerian” setting
obtained by Lovász and Cherkassky independently in the ’70s.

###### Key words and phrases:

Lovász-Cherkassky theorem, T-path, packing paths

###### 2020 Mathematics Subject Classification:

Primary: 05C63 Secondary: 05C38, 05C40, 05C45

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation)-513023562 and partially by NKFIH OTKA-129211

##  1\. Introduction

###  1.1. Motivation

Paul Erdős was one of the most influential mathematicians in modern
combinatorics. One of his excellent qualities was the ability to work equally
well with finite and infinite combinatorial structures. He conjectured as a
student that Menger’s theorem remains true in infinite graphs in the following
structural sense: For every directed graph $D$ and $A,B\subseteq V(D)$, there
is a family $\mathcal{P}$ of disjoint directed $AB$-paths and an
$AB$-separator $S$ consisting of precisely one vertex from each path in
$\mathcal{P}$. This conjecture gave a great amount of work for several
mathematicians (Podewski, Steffens, Aharoni, Berger, Nash-Williams, Shelah,
etc.) for decades after it was eventually proved in its whole generality [5].
It also inspired Aharoni and Nash-Williams, who themselves also have a
significant contribution both to finite and infinite combinatorics, to
formulate conjectures in infinite combinatorics extending their finite
counterparts.

For example, Aharoni conjectured that if all the finite induced subgraphs of a
graph are perfect and it does not contain an infinite independent set of
vertices, then it admits a vertex-colouring where there is no monochromatic
edge and there is a clique on which all colours appear. This was verified for
chordal graphs in [8]. Nash-Williams’ conjecture about the intersection of
infinite matroids (see [12]) generalizes structurally the Matroid intersection
theorem of Edmonds and is an active research direction [13, 16, 26]. His
conjecture about the existence of a $k$-arc-connected orientation of
$2k$-edge-connected graphs, that he proved for finite graphs, is also
intensively investigated [36, 14].

These examples indicate that (structural) infinite generalizations of
classical theorems in finite combinatorics are rich sources of deep, new
mathematical ideas. The starting point of our investigation is a theorem
obtained by Lovász and Cherkassky independently in the ’70s. We need to
introduce a few notions to state it.

###  1.2. The main result

A grapht $G$ is a graph together with a fixed subset $T$ of vertices. A grapht
is inner Eulerian if there is no vertex set $X$ disjoint from $T$ that defines
an odd cut111In a finite grapht assuming this only for singletons implies that
this holds for every $X$.. A $T$-path is a path between two distinct elements
of $T$ without inner points in $T$. For disjoint $X,Y\subseteq V(G)$, let
$\lambda_{G}(X,Y)$ denote the maximal number of pairwise edge-disjoint paths
between $X$ and $Y$ in $G$.

######  Theorem 1.1 (Lovász-Cherkassky theorem, [29, 18]).

In every finite, inner Eulerian grapht $G$ the maximal number of pairwise
edge-disjoint $T$-paths is equal to

$\frac{1}{2}\sum_{t\in T}\lambda_{G}(t,T-t).$

If $\mathcal{P}$ is a system of edge-disjoint $T$-paths, then
$\left|\mathcal{P}\right|$ can be calculated by counting for each $t\in T$ how
many $P\in\mathcal{P}$ has $t$ as an end-vertex and dividing the sum of these
quantities by two. Since $\lambda_{G}(t,T-t)$ is clearly an overestimation of
the number of paths between $t$ and $T-t$ in $\mathcal{P}$, the expression in
Theorem 1.1 is indeed an upper bound for the maximal size of a family of edge-
disjoint $T$-paths (regardless if $G$ is inner Eulerian). Having
$\lambda_{G}(t,T-t)$ paths in $\mathcal{P}$ ending at $t$ can be rephrased via
Menger’s theorem by the existence of a cut separating $t$ and $T-t$ that
consists of precisely one edge from each $P\in\mathcal{P}$ ending at $t$. The
equality in Theorem 1.1 means that such a cut exists for each $t$. This
indicates a structural formulation of Theorem 1.1. The main result of this
paper is that this structural formulation222The literal, quantitative infinite
generalization also holds but, as in the case of Menger’s theorem, it is much
weaker than the structural one. is true regardless of the size of $G$:

######  Theorem 1.2 (Infinite Lovász-Cherkassky theorem).

In every inner Eulerian graft $G$ there exists a system $\mathcal{P}$ of edge-
disjoint $T$-paths such that for every $t\in T$ there is a cut separating $t$
and $T-t$ that consists of precisely one edge from each path in $\mathcal{P}$
that has $t$ as an end-vertex.

###  1.3. Difficulties compared to the finite version

In order to prove Theorem 1.2, we are facing some difficulties that are not
arising if only finite graphts are considered. Some of the proofs of the
finite version start with a hypothetical counterexample for which
$\left|V\right|+\left|E\right|$ is minimal, reduces this quantity by one in a
way, uses the fact that the result is no longer a counterexample and shows
based on that, the original was also not a counterexample. Since reducing an
infinite cardinal by one is not meaningful, such proofs cannot be adapted
directly.

There exists an augmenting path based algorithm for the ‘packing edge-disjoint
$T$-paths’ problem [24] that also works in the infinite (not necessarily inner
Eulerian) setting. Even so, in general no well-defined limit object can be
guaranteed after infinitely many iterations of augmenting paths.

A key observation in Lovász’ proof is that for each $t\in T$ all the numbers
in

$\\{d(X):\ t\in X\subseteq V\setminus(T-t)\\}$

have the same parity (namely the parity of $d(t)$). Indeed, the sum
$\sum_{x\in X}d(x)$ is equal to $d(X)$ plus twice the number of edges spanned
by $X$ and all summands except maybe $d(t)$ are even. This allows Lovász to
delete two edges “safely” in a certain setting applying Menger’s theorem and
the fact that if $m<n$ and they have the same parity then $m+2\leq n$. Parity-
based arguments do not work in the infinite case because all the involved
cardinals might be infinite as well as $X$ itself.

Despite of these hindrances some of the ideas in Lovász’ proof can be adapted.
The ‘safe deletion of two edges’ by Lovász plays an important role in our
proof as well (Lemma 6.3) but the parity-based argument needs to be replaced
by a more complex structural one. The ‘splitting off’ technique of Lovász also
appears in our proof. It does not reduce $\left|E\right|$ in general but it
reduces a finite quantity associated with a hypothetical counterexample for
Lemma 6.5. To handle uncountable graphs, the key is (beyond elementary
submodels and singular compactness) Lemma 5.4 which was inspired by the works
of Aharoni, Nash-Williams and Shelah on the existence of transversals [9, 10].
Roughly speaking, the abstraction of their idea says that if we have an
uncountable structure with a certain property and consider an increasing,
continuous sequence of substructures whose length is an uncountable regular
cardinal, then (in the right setting) there is a closed, unbounded subset of
terms each of whose removal preserves the condition in question. The exact
implementation of this abstract idea varies from problem to problem (see [3,
4, 5]). In our case we can maintain in Lemma 5.4 only a weakening of the
property that we initially assumed. Even so, being aware of their technique
was essential in guiding our proof efforts in the right direction.

###  1.4. The structure of the paper

In Section 2 we introduce the notation. The former results we need for the
proof are summarized in Section 3. The proof of the main result is divided
into three sections.

In the first one (Section 4), we discuss a simple method to “lift up” systems
of edge-disjoint $T$-paths to the original grapht that are obtained after
certain contractions. In particular, we reduce the main result to a theorem
(Linkage theorem 4.1) in which we want to cover every edge incident with any
$t\in T$ by a system of edge-disjoint $T$-paths under the condition that for
any single $t\in T$, the edges incident with $t$ can be covered by such a
system. The proofs of this section are relatively simple. They are based on
the iterated application of the infinite Menger’s theorem [5] and the infinite
version of Pym’s theorem [19].

Section 5 is dedicated to the reduction of the Linkage theorem to its special
case where the grapht is countable. Only this section requires some basic
knowledge about combinatorial set theory (stationary sets and elementary
submodels). The already mentioned Lemma 5.4 plays a key role by guaranteeing
that we can maintain the premise of the Linkage theorem “most of the time”
while cutting up an uncountable grapht into smaller pieces.

In Section 6, we prove the countable case of the Linkage theorem. This is a
somewhat simplified version of our previous work [28] in which we solved the
countable case of the problem. We decided to include this for the sake of
completeness but moved it to the end, thus readers already familiar with the
proof of the countable case can skip it.

In the last section (Section 7), we formulate a “meta-conjecture” together
with a couple of specific conjectures concerning infinite generalizations of
further classical results.

##  2\. Notation

###  2.1. Graph theory

In graphs, we allow parallel edges but not loops. Technically we represent a
graph as a triple $\bm{G=(V,E,I)}$ where the _incidence function_
$\bm{I}:E\rightarrow[V]^{2}$ determines the end-vertices of the edges. An
edge-partition of a graph $G$ is a family of subgraphs whose edge sets
partition $E(G)$. For $X\subseteq V$ let $\bm{\delta_{G}(X)}:=\\{e\in
E:\left|I(e)\cap X\right|=1\\}$ and we write $\bm{d_{G}(X)}$ for
$\left|\delta_{G}(X)\right|$. If a grapht $G$ is obvious from the context,
then we omit the subscript, furthermore, for a singleton $\\{x\\}$ we write
simply $\delta(x)$ and $d(x)$. All the paths in the paper are finite. For
disjoint $A,B\subseteq V$ an $\bm{AB}$-path is a path with one endpoint in $A$
the other in $B$ and no internal vertices in $A\cup B$. Sometimes we need to
combine paths to obtain new ones. We illustrate our notation by an example:
Let $P$ and $Q$ be paths with $s\in V(P)$, $t\in V(Q)$ and $e\in E(P)\cap
E(Q)$. Then $\bm{sPeQt}$ is the graph that consists of the smallest subpath of
$P$ containing $s$ and $e$ and the smallest subpath of $Q$ containing $t$ and
$e$. We use this only when the resulting graph is also a path. We call
$C\subseteq E$ a _cut_ if $C=\delta(X)$ for some $X\subseteq V$. It is an
$\bm{AB}$-cut if $G-C$ does not contain any $AB$-path. We say that the edge
set $C$ and the system $\mathcal{P}$ of edge-disjoint paths are _orthogonal_
to each other if $C$ consists of one edge from each $P\in\mathcal{P}$. An
_Erdős-Menger_ $AB$_-cut_ is an $AB$-cut $C$ for which there exists a system
$\mathcal{P}$ of edge-disjoint $AB$-paths such that $C$ is orthogonal to
$\mathcal{P}$. The $\bm{A}$-side of an $AB$-cut $C$ is the set of vertices
reachable from $A$ without using edges from $C$. For a $U\subseteq V$ and a
family $\mathcal{F}=\\{X_{u}:u\in U\\}$ of pairwise disjoint subsets of $V$
with $X_{u}\cap U=\\{u\\}$, we define the graph $\bm{G/\mathcal{F}}$ obtained
from $G$ by _contracting_ $X_{u}$ to $u$ for $u\in U$ and deleting the
resulting loops. Formally,
$V(G/\mathcal{F}):=(V\setminus\bigcup\mathcal{F})\cup U,\
E(G/\mathcal{F}):=E\setminus\\{e\in E:(\exists u\in U)I(e)\subseteq X_{u}\\}$
and $I(G/\mathcal{F})(e):=\\{i_{\mathcal{F}}(u),i_{\mathcal{F}}(v)\\}$ where
$I(e)=\\{u,v\\}$ and

$i_{\mathcal{F}}(v)=\begin{cases}v&\mbox{if }v\notin\bigcup\mathcal{F}\\\
u&\mbox{if }u\in X_{u}.\end{cases}$

A quadruple $\bm{G=(V,E,I,T)}$ is a _grapht_ if $(V,E,I)$ is a graph and
$T\subseteq V$ with $\left|T\right|\geq 2$. Definitions corresponding to
graphs are extended to graphts in the natural way. We refer to the elements of
$T$ as _terminal points_. A grapht is inner Eulerian if there is no
$X\subseteq V\setminus T$ where $d(X)$ is an odd natural number. A $T$_-path_
is a path between two distinct terminal points without inner points in $T$.
For $t\in T$, we write $t$-cut as an abbreviation of $t(T-t)$-cut. A system
$\mathcal{P}$ of edge-disjoint $T$-paths _links_ $t$ if it covers $\delta(t)$.
It is a _linkage_ for $t\in T$ if links $t$ and minimal with respect to this
property (i.e. each $P\in\mathcal{P}$ ends in $t$). We say that $t$ is linked
if there is a $\mathcal{P}$ that links it. Finally, $\mathcal{P}$ is a
_perfect linkage_ of $G$ if it links every $t\in T$. A grapht satisfies the
_linkability condition_ if every $t\in T$ is linked in it. For a set $M$ and
grapht $G$, we abuse the notation and let

$\displaystyle\bm{G\cap M}$ $\displaystyle:=(V,E\cap
M,I\\!\\!\upharpoonright\\!\\!(E\cap M),T)$ $\displaystyle\bm{G\setminus M}$
$\displaystyle:=(V,E\setminus M,I\\!\\!\upharpoonright\\!\\!(E\setminus
M),T).$

###  2.2. Set theory

We use standard set-theoretic notation. The variables $\alpha,\beta$ and
$\gamma$ are standing for ordinal numbers, while $\kappa$ denotes cardinals.
The smallest infinite cardinal, i.e. the set of the natural numbers is denoted
by $\bm{\omega}$. The cofinality of $\kappa$ is $\bm{\mathsf{cf}(\kappa)}$.
Let $\kappa$ be an infinite cardinal. A sequence $\left\langle M_{\alpha}:\
\alpha<\kappa\right\rangle$ of sets is increasing ($\in$-increasing) if
$M_{\beta}\subseteq M_{\alpha}$ ($M_{\beta}\in M_{\alpha}$) for every
$\beta<\alpha<\kappa$. An increasing sequence is continuous if
$M_{\alpha}=\bigcup_{\beta<\alpha}M_{\beta}$ for each limit ordinal
$\alpha<\kappa$. Suppose that $\kappa=\mathsf{cf}(\kappa)>\omega$. A set
$C\subseteq\kappa$ is a _club_ of $\kappa$ if it is unbounded in $\kappa$ and
closed with respect to the order topology (i.e. $\sup B:=\bigcup B\in C$ for
every $B\subseteq C$ bounded in $\kappa$). A set $S\subseteq\kappa$ is
_stationary_ in $\kappa$ if it meets every club of $\kappa$.

###  2.3. Elementary submodels

Let $\varphi$ be a formula in the first-order language of set theory with free
variables $v_{1},\dots,v_{n}$. For a set $M$, the formula $\varphi^{M}$ is
obtained from $\varphi$ by the relativization of the quantifiers to $M$ (i.e.
$\forall v(\dots)$ is replaced by ${\forall v(v\in M\Longrightarrow(\dots))}$
and $\exists v(\dots)$ by $\exists v(v\in M\wedge(\dots))$). The set $M$ is a
$\varphi$-elementary submodel of the universe333It is also common to
approximate the universe by a “big” but set-sized structure first and take
elementary submodels of that. From the perspective of applications, it does
not make a difference. if for every $x_{1},\dots,x_{n}\in M$ we have
$\varphi(x_{1},\dots,x_{n})\Longleftrightarrow\varphi^{M}(x_{1},\dots,x_{n})$.
Let $\Sigma$ be a finite set of formulas. Then we say that $M$ is a
$\Sigma$-elementary submodel of the universe if $M$ is $\varphi$-elementary
for each $\varphi\in\Sigma$.

Let a finite set $\Sigma$ of formulas, that contains everything relevant for
our proofs, be fixed through the paper. To improve the flow of words, we say
simply “elementary submodel” instead of “$\Sigma$-elementary submodel of the
universe”. For more details concerning elementary submodels, we refer to [34].

##  3\. Preliminaries

######  Lemma 3.1 (Fodor’s lemma, [25, Theorem 8.7]).

If $\kappa=\mathsf{cf}(\kappa)>\omega$, $S\subseteq\kappa$ is stationary and
$f:S\rightarrow\kappa$ is a regressive function (i.e. $f(\alpha)<\alpha$ for
every $\alpha\in S\setminus\\{0\\}$), then there is a stationary
$S^{\prime}\subseteq S$ and a $\gamma<\kappa$ such that $f(\alpha)=\gamma$ for
each $\alpha\in S^{\prime}$.

######  Theorem 3.2 (Nash-Williams, [32, p. 235 Theorem 3]).

A graph $G$ can be edge-partitioned into cycles if and only if there is no cut
$C$ in $G$ such that $\left|C\right|$ is an odd natural number.

######  Corollary 3.3.

A grapht can be edge-partitioned into cycles and $T$-paths if and only if it
is inner Eulerian.

###### Proof.

On the one hand, being inner Eulerian is clearly necessary because for
$X\subseteq V(G)\setminus T$, the contribution of a $T$-path or a cycle to
$d_{G}(X)$ is even. On the other hand, $G$ being inner Eulerian means that the
graph $G/T$ we obtain from $G$ by contracting $T$ into a single point has no
odd cuts. Thus by Theorem 3.2, $G/T$ admits an edge-partition into cycles
which provides an edge-partition of $G$ into cycles and $T$-paths. ∎

Menger’s theorem and the other connectivity-related results that we recall
have four versions depending on whether the graph is directed and if we
consider vertex-disjoint or edge-disjoint paths. We state always just the
undirected edge-variant which can be derived from any other versions.

Let a grapht $G=(V,E,I,\\{s,t\\})$ be fixed for the rest of the section.

######  Theorem 3.4 (Aharoni and Berger, [5]).

There is a system $\mathcal{P}$ of edge-disjoint $st$-paths and an $st$-cut
$C$ which is _orthogonal_ to $\mathcal{P}$.

######  Theorem 3.5 (Diestel and Thomassen, [19]).

Let $\mathcal{P}$ and $\mathcal{Q}$ be systems of edge-disjoint $st$-paths.
Then there exists a system $\mathcal{R}$ of edge-disjoint $st$-paths such that
$\delta_{\mathcal{R}}(s)\supseteq\delta_{\mathcal{P}}(s)$ and
$\delta_{\mathcal{R}}(t)\supseteq\delta_{\mathcal{Q}}(t)$.

For Erdős-Menger $st$-cuts $C$ and $C^{\prime}$, we write $C\trianglelefteq
C^{\prime}$, if for every $st$-path $P$ if $<_{P}$ is the linear order on
$E(P)$ corresponding to the $s\rightarrow t$ direction of $P$, then
$\min_{<_{P}}(C\cap E(P))\leq\min_{<_{P}}(C^{\prime}\cap E(P))$. These
definitions extend naturally for the setting where we have disjoint, nonempty
sets $S$ and $T$ instead of distinct points $s$ and $t$ by contracting $S$ and
$T$ to one of their respective elements.

######  Theorem 3.6 ([27]).

The Erdős-Menger $st$-cuts form a complete lattice with respect to
$\trianglelefteq$.

######  Lemma 3.7 (Augmenting paths for Menger’s theorem, [15]).

Let $\mathcal{P}$ be a system of edge-disjoint $st$-paths. Then there exists

  1. (1)

either an $st$-cut $C$ orthogonal to $\mathcal{P}$,

  2. (2)

or a system $\mathcal{Q}$ of edge-disjoint $st$-paths for which
$\mathcal{P}\triangle\mathcal{Q}$ is finite,
$\delta_{\mathcal{Q}}(s)\supset\delta_{\mathcal{P}}(s)$ with
$\left|\delta_{\mathcal{Q}}(s)\setminus\delta_{\mathcal{P}}(s)\right|=1$ and
$\delta_{\mathcal{Q}}(t)\supset\delta_{\mathcal{P}}(t)$ with
$\left|\delta_{\mathcal{Q}}(t)\setminus\delta_{\mathcal{P}}(t)\right|=1$.

For the following couple of lemmas, we could not find really fitting
references, thus we include their short proofs. As far we know, the phenomenon
of “tight” sets in the context of the infinite version of König’s theorem [3]
and beyond was discovered by Podewski and Steffens [33, 35] and it is known
that it holds in the context of the infinite Menger’s theorem as well:

######  Lemma 3.8.

Suppose that $s$ is linked and every path-system that links $s$ uses the edge
$e\in E\setminus\delta(s)$. Then the $\trianglelefteq$-smallest Erdős-Menger
$st$-cut $C$ that contains $e$ is _tight_ in the sense that every linkage of
$s$ is orthogonal to $C$.

###### Proof.

Suppose for a contradiction that $G$ and $e$ form a counterexample. We can
assume without loss of generality that $C=\delta_{G}(t)$ because after the
contraction of the $t$-side of $C$ to $t$, it remains a counterexample. By the
indirect assumption there exists a linkage $\mathcal{P}$ for $s$ that does not
cover $\delta_{G}(t)$. Let $P_{e}$ be the unique path in $\mathcal{P}$ through
$e$. By applying Lemma 3.7 with the path-system $\mathcal{P}-P_{e}$ in $G-e$,
the alternative (2) is impossible because the resulting path-system
$\mathcal{Q}$ would cover $\delta_{G^{\prime}}(s)=\delta_{G}(s)$ without using
$e$. It follows that there is an $st$-cut $C^{\prime}$ in $G-e$ orthogonal to
$\mathcal{P}-P_{e}$. The path $P_{e}-e$ lives in $G-e$ and does not meet
$C^{\prime}$, thus $C^{\prime}+e$ is an Erdős-Menger $st$-cut in $G$ with the
same sides as $C^{\prime}$. Clearly
$C^{\prime}+e\trianglelefteq\delta_{G}(t)$. Furthermore,
$C^{\prime}+e\neq\delta_{G}(t)$ because $C^{\prime}+e$ is orthogonal to
$\mathcal{P}$ and $\delta(t)$ is not. This contradicts the
$\trianglelefteq$-minimality of $C$. ∎

The following lemma is about a fundamental property of the so-called
(infinite) gammoids [17, 1]:

######  Lemma 3.9.

Suppose that $\mathcal{P}$ is a linkage of $s$ with $\left|\delta(t)\setminus
E(\mathcal{P})\right|=1$ and there is no linkage $\mathcal{P}^{\prime}$ for
$s$ with $\delta_{\mathcal{P}^{\prime}}(t)\subsetneq\delta_{\mathcal{P}}(t)$.
Then $\left|\delta(t)\setminus E(\mathcal{Q})\right|\leq 1$ holds for every
linkage $\mathcal{Q}$ for $s$.

###### Proof.

Let $e$ be the unique element of $\delta(t)\setminus E(\mathcal{P})$. Suppose
for a contradiction that there exists a linkage $\mathcal{Q}$ for $s$ with
$\left|\delta(t)\setminus E(\mathcal{Q})\right|>1$. Then we must have $e\in
E(\mathcal{Q})$, since otherwise $\mathcal{P}^{\prime}=\mathcal{Q}$
contradicts the premise of the lemma. Let $Q_{e}$ be the unique path in
$\mathcal{Q}$ through $e$ and let $\mathcal{Q}^{\prime}:=\mathcal{Q}-Q_{e}$.
By applying Lemma 3.7 with the path-system $\mathcal{Q}^{\prime}$ in $G-e$ the
alternative (2) is impossible because the resulting path-system
$\mathcal{P}^{\prime}$ would contradict the premise of the lemma. It follows
that there is an $st$-cut $C$ in $G-e$ orthogonal to $\mathcal{Q}^{\prime}$.
But then the path-system $\mathcal{P}^{\prime}$ that we obtain by taking each
$P\in\mathcal{P}$ from $s$ until the first common edge $e_{P}$ with $C$ and
continue up to $t$ along the unique path in $\mathcal{Q}^{\prime}$ through
$e_{P}$ contradicts again the premise of the lemma. ∎

##  4\. Reduction to the Linkage theorem

In order to cover $\bigcup_{t\in T}\delta_{G}(t)$ by edge-disjoint $T$-paths,
i.e. to have a perfect linkage, it is obviously necessary that for each
individual $t\in T$ the edge set $\delta_{G}(t)$ can be covered by such paths,
i.e. that the linkability condition holds. Maybe surprisingly, in the inner
Eulerian case this is already sufficient as well:

######  Theorem 4.1 (Linkage theorem).

Every inner Eulerian graft that satisfies the linkability condition admits a
perfect linkage.

In the rest of the section, we show that Theorem 4.1 implies our main result
1.2 and introduce some tools that we need later.

Let a grapht $G=(V,E,I,T)$ be fixed for the rest of the section.

######  Observation 4.2 (Lifting lemma).

Let $\mathcal{F}=\\{X_{t}:\ t\in T\\}$ be a family of pairwise disjoint
subsets of $V$ where $t\in X_{t}$ and $X_{t}$ is _boundary-linked_ in the
sense that there is a system $\mathcal{P}_{t}=\\{P_{t,e}:\
e\in\delta_{G}(X_{t})\\}$ of edge-disjoint paths where $e$ is the first edge
and $t$ is the last vertex of $P_{t,e}$ (in suitable orientation).

Then for every system $\mathcal{P}$ of edge-disjoint $T$-paths in
$G/\mathcal{F}$, there is a system $\mathcal{P}^{\prime}$ of edge-disjoint
$T$-paths in $G$ such that for every $P\in\mathcal{P}$ there is a
$P^{\prime}\in\mathcal{P}^{\prime}$ has the same endpoints as $P$ and
$E(P^{\prime})\supseteq E(P)$. Furthermore, this $\mathcal{P}^{\prime}$ can be
chosen in such a way that it links $t$ for every $t\in T$ for which
$\mathcal{P}$ links $t$ and $\mathcal{P}_{t}$ covers $\delta_{G}(t)$.

###### Proof.

For a $P\in\mathcal{P}$ we obtain $P^{\prime}$ by uniting $P$ and the paths
$P_{t_{i},e_{i}}$ for $i\in\\{0,1\\}$ where $t_{0}$ and $t_{1}$ are the
endpoints of $P$ and $e_{i}$ is the unique edge of $P$ incident with $t_{i}$
in $G/\mathcal{F}$ (see Figure 1).

$t_{0}$$t_{1}$$t_{2}$$e_{1}$$e_{0}$$P$$P_{t_{1},e_{1}}$$P_{t_{0},e_{0}}$
Figure 1. The Lifting lemma (Observation 4.2)

∎

######  Lemma 4.3.

For every $T^{\prime}\subseteq T$ there exists a family
$\mathcal{F}=\\{X_{t}:\ t\in T\\}$ of disjoint vertex sets with $t\in X_{t}$
such that $X_{t}=\\{t\\}$ for $t\in T\setminus T^{\prime}$ and for each $s\in
T^{\prime}$: $\delta(X_{s})$ is the $\trianglelefteq$-largest Erdős-Menger
$X_{s}(\bigcup_{t\in T-s}X_{t})$-cut. Every such $\mathcal{F}$ has the
following properties:

  1. (i)

For each $t\in T$ for which $t$ is linked in $G$ there is a system
$\mathcal{P}_{t}=\\{P_{t,e}:\ e\in\delta_{G}(X_{t})\\}$ of edge-disjoint paths
covering $\delta_{G}(t)$ where $e$ is the first edge and $t$ is the last
vertex of $P_{t,e}$ (in suitable orientation);

  2. (ii)

For every $t\in T^{\prime}$: $\delta_{G/\mathcal{F}}(t)$ is the unique Erdős-
Menger $t$-cut in $G/\mathcal{F}$;

  3. (iii)

If $G/\mathcal{F}$ has a perfect linkage then $G$ has a system $\mathcal{P}$
of $T$-paths with the properties described in Theorem 1.2.

###### Proof.

To show the existence, let $T^{\prime}=\\{t_{\alpha}:\ \alpha<\kappa\\}$. If
$X_{\beta}$ is already defined for $\beta<\alpha$, then we contract
$X_{\beta}$ to $t_{\beta}$ for each $\beta<\alpha$ and define $X_{\alpha}$ as
the $t_{\alpha}$-side of the $\trianglelefteq$-largest Erdős-Menger
$t_{\alpha}$-cut of the resulting grapht.

To show (i), observe that whenever $\delta_{G}(X_{t})$ is an Erdős-Menger
$t$-cut with $t\in X_{t}$, then $X_{t}$ is boundary-linked (in the sense of
Observation 4.2). If in addition $t$ is linked in $G$, then we claim that
Theorem 3.5 allows us to choose the path-system $\mathcal{P}_{t}$ witnessing
being boundary-linked in such a way that it covers $\delta_{G}(t)$. Indeed,
contract $V\setminus X_{t}$ to an $s\in T\setminus V$. Then in the resulting
grapht $G^{\prime}$ both $s$ and $t$ are linked, thus by Theorem 3.5 one can
link both by a single path-system.

Property (ii) holds because any further Erdős-Menger $t$-cut in
$G/\mathcal{F}$ would be an Erdős-Menger $X_{t}(\bigcup_{t^{\prime}\in
T-t}X_{t^{\prime}})$-cut in $G$ that is strictly $\trianglelefteq$-larger than
the largest one. Finally, (iii) follows by lifting up a perfect linkage of
$G/\mathcal{F}$ to $G$ in the sense of Lemma 4.2 because then the cuts
$\delta_{G}(X_{t})$ for $t\in T$ are as demanded by Theorem 1.2. ∎

######  Corollary 4.4.

Theorem 1.2 is implied by Theorem 4.1.

###### Proof.

It follows directly from (iii) of Lemma 4.3. ∎

######  Remark 4.5.

The proof also shows that the family of cuts in Theorem 1.2 can be chosen to
be nested.

##  5\. Reduction of the Linkage theorem to countable graphts

In this section, we reduce the Linkage theorem 4.1 to its special case where
the edge set of the grapht is countable.

###  5.1. Basic elementarity arguments

######  Observation 5.1.

If $M$ is an elementary submodel and $G\in M$ is an inner Eulerian grapht,
then the grafts $G\cap M$ and $G\setminus M$ are also inner Eulerian.

###### Proof.

By Corollary 3.3 we can fix an edge-partition $\mathcal{A}\in M$ of $G$ into
cycles and $T$-paths. Then if $e\in E\cap M$, then the unique
$H_{e}\in\mathcal{A}$ that contains $e$ is definable from the parameters
$\mathcal{A}$ and $e$, thus $H_{e}\in M$. Since $H_{e}$ is finite, this
implies $E(H_{e})\subseteq M$. This shows that there is no $H\in\mathcal{A}$
for which both $E(H)\cap M$ and $E(H)\setminus M$ are nonempty. But then
$\mathcal{A}\cap M$ and $\mathcal{A}\setminus M$ witness respectively that
$G\cap M$ and $G\setminus M$ are inner Eulerian. ∎

######  Observation 5.2.

If $M$ is an elementary submodel and $G\in M$ is a grapht satisfying the
linkability condition, then the graft $G\cap M$ also satisfies the linkability
condition.

###### Proof.

For $t\in T\setminus M$ we have $\delta_{G\cap M}(t)=\emptyset$, thus $t$ is
linked in $G\cap M$. For $t\in T\cap M$ let $\mathcal{P}_{t}\in M$ be a path-
system that links $t$ in $G$. For each $e\in\delta_{G}(t)\cap M=\delta_{G\cap
M}(t)$, the unique $P_{e}\in\mathcal{P}_{t}$ through $e$ is definable from the
parameters $\mathcal{P}_{t}$ and $e$, therefore $P_{e}\in M$ and hence
$E(P_{e})\subseteq M$. Thus $\mathcal{P}_{t}\cap M$ links $t$ in $G\cap M$. ∎

######  Observation 5.3.

If $M$ is an elementary submodel and $G\in M$ is a grapht satisfying the
linkability condition, then every $t\in T\cap M$ is linked in $G\setminus M$.

###### Proof.

Let $t\in T\cap M$ be fixed and take a system $\mathcal{P}_{t}\in M$ that
links $t$. We claim that for $e\in\delta(t)\setminus M$ the unique
$P_{e}\in\mathcal{P}_{t}$ through $e$ cannot have any edges in $M$. Indeed, if
$f\in E(P_{e})\cap M$, then $P_{e}$ is definable from the parameters $f$ and
$\mathcal{P}_{t}$, thus $P_{e}\in M$ but then $e\in E(P_{e})\subseteq M$ which
contradicts the choice of $e$. Therefore the path-system
$\mathcal{P}_{t}\setminus M$ links $t$ in $G\setminus M$. ∎

The linkability of a $t\in T\setminus M$ in $G\setminus M$ will take more
effort, we handle it by a “workaround” in the following subsection.

###  5.2. Stationarily many violations cannot occur

######  Lemma 5.4.

Suppose that $\kappa$ is an uncountable regular cardinal, $\left\langle
M_{\alpha}:\ \alpha<\kappa\right\rangle$ is an increasing, continuous sequence
of elementary submodels with $\left\langle M_{\beta}:\
\beta\leq\alpha\right\rangle\in M_{\alpha+1}$ and
$\left|M_{\alpha}\right|<\kappa$ for each $\alpha<\kappa$ and $G=(V,E,I,T)\in
M_{0}$ is a grapht such that $\delta(t)$ is the unique Erdős-Menger $t$-cut
for $t\in T$. Then there is a club $U$ of $\kappa$ such that for $\alpha\in U$
the grapht $G\setminus M_{\alpha}$ satisfies the linkability condition.

###### Proof.

Let $S\subseteq\kappa$ be the set of those ordinals $\alpha$ for which the
linkability condition fails in $G\setminus M_{\alpha}$. Suppose for a
contradiction that $S$ is stationary. Let $\left\langle\alpha_{\xi}:\
\xi<\kappa\right\rangle$ be the increasing enumeration of $S$. Fix a well-
order $\prec$ of $T$ that is in $M_{0}$. We define $X_{\xi}\subseteq V$ and
$t_{\xi}\in T$ for $\xi<\kappa$ by transfinite recursion such that (see Figure
2):

  1. (1)

the sets $X_{\xi}$ are pairwise disjoint,

  2. (2)

$X_{\xi}\cap T=\\{t_{\xi}\\}$,

  3. (3)

$\delta_{G\setminus M_{\alpha_{\xi}}}(X_{\xi})$ is an Erdős-Menger
$t_{\xi}$-cut in $G\setminus M_{\alpha_{\xi}}$,

  4. (4)

$\delta_{G}(X_{\xi})\cap M_{\alpha_{\xi}}\neq\emptyset$,

  5. (5)

$X_{\xi}$ and $t_{\xi}$ are definable from the parameters $G,\ \left\langle
M_{\alpha}:\ \alpha\leq\alpha_{\xi}\right\rangle$ and $\prec$.

$t_{\xi}$$M_{\alpha_{\xi}}$$t_{\eta}$$X_{\xi}$$X_{\eta}$ Figure 2. The choice
of $t_{\xi}$ and $X_{\xi}$.

Let $\xi<\kappa$ and suppose that $t_{\eta}$ and $\ X_{\eta}$ are defined for
$\eta<\xi$ such that the conditions (1)-(5) are obeyed so far. The linkability
condition fails in $G\setminus M_{\alpha_{\xi}}$ by assumption. Let
$t_{\xi}\in T$ be the $\prec$-smallest witness for this. Note that we must
have $t_{\xi}\in T\setminus M_{\alpha_{\xi}}$ by Observation 5.3 and hence
$\delta_{G\setminus M_{\alpha_{\xi}}}(t_{\xi})=\delta_{G}(t_{\xi})$. Let
$G_{\xi}$ be the grapht we obtain from $G\setminus M_{\alpha_{\xi}}$ by
contracting $X_{\eta}$ to $t_{\eta}$ for every $\eta<\xi$. Note that $G_{\xi}$
is definable from the parameters $G,\ \left\langle M_{\alpha}:\
\alpha\leq\alpha_{\xi}\right\rangle$ and $\prec$.

######  Claim 5.5.

For every $\eta<\xi$: $\delta_{G\setminus M_{\alpha_{\xi}}}(X_{\eta})$ is an
Erdős-Menger $t_{\eta}$-cut in $G\setminus M_{\alpha_{\xi}}$ and hence
$X_{\eta}$ is boundary-linked w.r.t. $t_{\eta}$ in $G\setminus
M_{\alpha_{\xi}}$.

###### Proof.

Let $\eta<\xi$ be given. By condition (3), $\delta_{G\setminus
M_{\alpha_{\eta}}}(X_{\eta})$ is an Erdős-Menger $t_{\eta}$-cut in $G\setminus
M_{\alpha_{\eta}}$. Let $\mathcal{P}$ be a path-system that witnesses this.
Since $X_{\eta},M_{\alpha_{\eta}}\in M_{\alpha_{\xi}}$ we can assume that
$\mathcal{P}\in M_{\alpha_{\xi}}$. But then we claim that for every
$e\in\delta_{G\setminus M_{\alpha_{\xi}}}(X_{\eta})$ the unique
$P_{e}\in\mathcal{P}$ through $e$ has no edges in $M_{\alpha_{\xi}}$. Indeed,
if $f\in E(P_{e})\cap M_{\alpha_{\xi}}$ then $P_{e}\in M_{\alpha_{\xi}}$
because $P_{e}$ is definable from $f,\mathcal{P}\in M_{\alpha_{\xi}}$ but then
$P_{e}\in M_{\alpha_{\xi}}$ and hence $e\in E(P_{e})\subseteq
M_{\alpha_{\xi}}$ which contradicts $e\in\delta_{G\setminus
M_{\alpha_{\xi}}}(X_{\eta})$. Thus $\mathcal{P}\setminus M_{\alpha_{\xi}}$
witnesses that $\delta_{G\setminus M_{\alpha_{\xi}}}(X_{\eta})$ is an Erdős-
Menger $t_{\eta}$-cut in $G\setminus M_{\alpha_{\xi}}$. ∎

######  Corollary 5.6.

$t_{\xi}$ is not linked in $G_{\xi}$.

###### Proof.

Suppose for a contradiction that $\mathcal{P}$ links $t_{\xi}$ in $G_{\xi}$.
Then Claim 5.5 ensures that the Lifting lemma (Observation 4.2) is applicable
to $\mathcal{P}$ in $G\setminus M_{\xi}$ with the sets

$X_{t}:=\begin{cases}X_{\eta}&\mbox{if }t=t_{\eta}\text{ for some }\eta<\xi\\\
\\{t\\}&\mbox{if }t\in T\setminus\\{t_{\eta}:\ \eta<\xi\\}.\end{cases}$

Since $\delta_{G_{\xi}}(t_{\xi})=\delta_{G\setminus
M_{\alpha_{\xi}}}(t_{\xi})=\delta_{G}(t)$, we conclude that $t_{\xi}$ is
linked in $G\setminus M_{\alpha_{\xi}}$ which contradicts the choice of
$t_{\xi}$. ∎

We take the $\trianglelefteq$-largest Erdős-Menger $t_{\xi}$-cut in $G_{\xi}$
and define $X_{\xi}$ to be the $t_{\xi}$-side of it. The preservation of all
the properties but (4) follows directly from the construction. We show that
(4) is also preserved. It follows by the Lifting lemma (Observation 4.2) that
$\delta_{G_{\xi}}(X_{\xi})(=\delta_{G\setminus M_{\alpha_{\xi}}}(X_{\xi}))$ is
an Erdős-Menger $t_{\xi}$-cut in $G\setminus M_{\alpha_{\xi}}$ as well. Note
that $\delta_{G\setminus M_{\alpha_{\xi}}}(X_{\xi})\neq\delta_{G}(t_{\xi})$
because otherwise $t_{\xi}$ would be linked in $G\setminus M_{\alpha_{\xi}}$
by any path-system that witnesses that $\delta_{G\setminus
M_{\alpha_{\xi}}}(X_{\xi})$ is an Erdős-Menger $t_{\xi}$-cut in $G\setminus
M_{\alpha_{\xi}}$. Since $\delta_{G}(t_{\xi})$ is the only Erdős-Menger
$t_{\xi}$-cut in $G$ we conclude that $\delta_{G}(X_{\xi})$ is not an Erdős-
Menger $t_{\xi}$-cut in $G$. Therefore $\delta_{G}(X_{\xi})\cap
M_{\alpha_{\xi}}\neq\emptyset$ since otherwise any path-system that witnesses
that $\delta_{G}(X_{\xi})\cap M_{\alpha_{\xi}}\ $ is an Erdős-Menger
$t_{\xi}$-cut in $G\setminus M_{\alpha_{\xi}}$ also witnesses this in $G$
contradicting the uniqueness of $\delta_{G}(t_{\xi})$. The recursion is done.

Let $S^{\prime}$ be the set of limit ordinals in $S$. Then $S^{\prime}$ is
still stationary. For $\alpha_{\xi}\in S^{\prime}$ we let $f(\alpha_{\xi})$ be
the smallest ordinal $\beta$ with $\delta_{G}(X_{\xi})\cap
M_{\beta}\neq\emptyset$. This $f$ is well-defined because
$\delta_{G}(X_{\xi})\cap M_{\alpha_{\xi}}\neq\emptyset$ by (4). Furthermore,
$f(\alpha_{\xi})<\alpha_{\xi}$ because
$M_{\alpha_{\xi}}=\bigcup_{\beta<\alpha_{\xi}}M_{\beta}$ since $\left\langle
M_{\alpha}:\ \alpha<\kappa\right\rangle$ is continuous. By Fodor’s lemma
(Lemma 3.1) we can find a stationary $S^{\prime\prime}\subseteq S^{\prime}$
and a $\gamma<\kappa$ such that $f(\alpha)=\gamma$ for every $\alpha\in
S^{\prime\prime}$. Then each of the $\kappa$ many cuts $\delta_{G}(X_{\xi})$
$(\alpha_{\xi}\in S^{\prime\prime})$ meets $M_{\gamma}$ but an $e\in
M_{\gamma}$ can belong to at most two of them which is a contradiction because
$\left|M_{\gamma}\right|<\kappa$. ∎

######  Corollary 5.7.

Let $\kappa$ be an infinite cardinal, $\mathcal{X}$ a set of size at most
$\kappa$ and let $G=(V,E,I,T)$ be a grapht such that for every $t\in T$,
$\delta(t)$ is the unique Erdős-Menger $t$-cut. Then there exists an
elementary submodel $M$ of size $\kappa$ with $\mathcal{X}\cup\\{G\\}\subseteq
M$ such that $G\setminus M$ satisfies the linkability condition.

###### Proof.

We build a sequence as in Lemma 5.4 and find a club of suitable submodels. In
more detail: By transfinite recursion, we define an increasing, continuous
sequence $\left\langle M_{\alpha}:\ \alpha<\kappa^{+}\right\rangle$ of
elementary submodels with $\left\langle M_{\beta}:\
\beta\leq\alpha\right\rangle\in M_{\alpha+1}$,
$\left|M_{\alpha}\right|=\kappa$ and $\mathcal{X}\cup\\{G\\}\subseteq
M_{\alpha}$ for each $\alpha<\kappa^{+}$. Let $M_{0}$ be an elementary
submodel of size $\kappa$ with $\mathcal{X}\cup\\{G\\}\subseteq M_{0}$.
Suppose that $\alpha<\kappa^{+}$ and $M_{\beta}$ is already defined for
$\beta<\alpha$. If $\alpha$ is a limit ordinal we let
$M_{\alpha}:=\bigcup_{\beta<\alpha}M_{\beta}$. If $\alpha=\beta+1$, then we
let $M_{\beta+1}$ to be an elementary submodel of size $\kappa$ with
$\mathcal{X}\cup\\{G,\left\langle M_{\gamma}:\
\gamma\leq\beta\right\rangle\\}\subseteq M_{\beta+1}$. The recursion is done
and by Lemma 5.4 we can find not just one but club many elementary submodels
in the constructed sequence that are as desired. ∎

###  5.3. Induction and singular compactness

We prove Theorem 4.1 by transfinite induction on $\left|E\right|=:\kappa$. We
defer the proof of the case $\kappa\leq\omega$ and will return to it in
Section 6. Suppose now that $\kappa>\omega$. By Lemma 4.3 (applied with the
whole $T$) we can assume without loss of generality that for each $t\in T$,
$\delta(t)$ is the unique Erdős-Menger $t$-cut. Assume first that $\kappa$ is
regular. Let $\left\langle M_{\alpha}:\ \alpha<\kappa\right\rangle$ be an
increasing, continuous sequence of elementary submodels with $\left\langle
M_{\beta}:\ \beta\leq\alpha\right\rangle\in M_{\alpha+1}$ and
$\left|M_{\alpha}\right|<\kappa$ for each $\alpha<\kappa$ and $G\in M_{0}$.
Let $U$ be a club of $\kappa$ as in Lemma 5.4 and let
$\left\langle\alpha_{\xi}:\ \xi<\kappa\right\rangle$ be the increasing
enumeration of $U$. By Observation 5.1 and by the choice of $U$ we know for
each $\xi<\kappa$, that the grapht $G\setminus M_{\alpha_{\xi}}$ is inner
Eulerian and satisfies the linkability condition. Since $G,M_{\alpha_{\xi}}\in
M_{\alpha_{\xi+1}}$, we have $G\setminus M_{\alpha_{\xi}}\in
M_{\alpha_{\xi+1}}$. Thus by applying Observations 5.1 and 5.2 we conclude
that the graphts $G\cap M_{\alpha_{0}}=:G_{-1}$ and $(G\setminus
M_{\alpha_{\xi}})\cap M_{\alpha_{\xi+1}}=:G_{\xi}$ for $0\leq\xi<\kappa$ are
inner Eulerian and satisfy the linkability condition. By induction we can take
a perfect linkage $\mathcal{P}_{\xi}$ of $G_{\xi}$ for $-1\leq\xi<\kappa$.
Since the sequence $\left\langle M_{\alpha}:\ \alpha<\kappa\right\rangle$ is
continuous and $U$ is a club of $\kappa$, the subsequence $\left\langle
M_{\alpha_{\xi}}:\ \xi<\kappa\right\rangle$ is also continuous. Thus the
graphts $G_{\xi}$ form an edge-partition of $G$. But then
$\bigcup_{-1\leq\xi<\kappa}\mathcal{P}_{\xi}$ is a perfect linkage of $G$.

Now we turn to the case where $\kappa$ is singular. The proof in this case is
based on Shelah’s singular compactness technique. Let
$\left\langle\kappa_{\alpha}:\ \alpha<\mathsf{cf}(\kappa)\right\rangle$ be an
increasing, continuous sequence of cardinals with limit $\kappa$ in which
$\kappa_{0}\geq\mathsf{cf}(\kappa)$. We define a “matrix”

$\\{M_{\alpha,n}:\ \alpha<\mathsf{cf}(\kappa),n<\omega\\}$

of elementary submodels with the following properties:

  1. (1)

$\left|M_{\alpha,n}\right|=\kappa_{\alpha}$,

  2. (2)

$\kappa_{\alpha}\subseteq M_{\alpha,n}$,

  3. (3)

$M_{\alpha^{\prime},n^{\prime}}\in M_{\alpha,n}$ if either $n^{\prime}<n$ or
$n^{\prime}=n$ and $\alpha^{\prime}<\alpha$.

  4. (4)

$G\in M_{0,0}$,

  5. (5)

$G\setminus M_{\alpha,n}$ satisfies the linkability condition.

######  Fact 5.8 ([34, Claim 3.7]).

If $M$ is an elementary submodel with $X\in M$ and $\left|X\right|\subseteq
M$, then $X\subseteq M$.

######  Corollary 5.9.

We have $M_{\beta,n}\subseteq M_{\alpha,n}$ and $M_{\beta,n}\subseteq
M_{\beta,n+1}$ whenever $\beta<\alpha<\mathsf{cf}(\kappa)$ and $n<\omega$.

Let $M_{\alpha}:=\bigcup_{n<\omega}M_{\alpha,n}$ for
$\alpha<\mathsf{cf}(\kappa)$.

######  Lemma 5.10.

$M_{\alpha}=\bigcup_{\beta<\alpha}M_{\beta}$ for every limit ordinal
$\alpha<\mathsf{cf}(\kappa)$.

###### Proof.

Let a limit ordinal $\alpha<\mathsf{cf}(\kappa)$ be fixed. We start with the
easy direction: $M_{\alpha}\supseteq\bigcup_{\beta<\alpha}M_{\beta}$. Let
$\beta<\alpha$ be given. By Observation 5.9, $M_{\beta,n}\subseteq
M_{\alpha,n}$ for every $n<\omega$, therefore

$M_{\beta}=\bigcup_{n<\omega}M_{\beta,n}\subseteq\bigcup_{n<\omega}M_{\alpha,n}=M_{\alpha}.$

It remains to prove that $M_{\alpha}\subseteq\bigcup_{\beta<\alpha}M_{\beta}$.
To do so, it is enough to show that
$M_{\alpha,n}\subseteq\bigcup_{\beta<\alpha}M_{\beta}$ for each $n<\omega$.
Let $n<\omega$ be fixed. By Observation 5.9 we have $M_{\alpha,n}\in
M_{0,n+1}\subseteq M_{0}\subseteq\bigcup_{\beta<\alpha}M_{\beta}$. By property
(1), $\left|M_{\beta,n}\right|=\kappa_{\beta}$ and hence
$\left|M_{\beta}\right|=\kappa_{\beta}$ for each $\beta<\alpha$. We also know
that $\kappa_{\alpha}=\bigcup_{\beta<\alpha}\kappa_{\beta}$ since
$\left\langle\kappa_{\beta}:\ \beta<\mathsf{cf}(\kappa)\right\rangle$ is
continuous. Thus

$\left|M_{\alpha,n}\right|=\kappa_{\alpha}=\bigcup_{\beta<\alpha}\kappa_{\beta}\subseteq\bigcup_{\beta<\alpha}M_{\beta}.$

The set $\bigcup_{\beta<\alpha}M_{\beta}$ is an elementary submodel because it
is the union of a chain of elementary submodels. Since we have shown
$M_{\alpha,n}\in\bigcup_{\beta<\alpha}M_{\beta}$ and
$\left|M_{\alpha,n}\right|\subseteq\bigcup_{\beta<\alpha}M_{\beta}$ we may
conclude $M_{\alpha,n}\subseteq\bigcup_{\beta<\alpha}M_{\beta}$ by Fact 5.8. ∎

######  Lemma 5.11.

For every $\alpha<\mathsf{cf}(\kappa)$ and $n<\omega$, the grapht
$G_{\alpha,n}:=G\cap(M_{\alpha,n}\setminus M_{\alpha,n-1})$ has a perfect
linkage $\mathcal{P}_{\alpha,n}$ (where $M_{\alpha,-1}:=\emptyset$).

###### Proof.

The premise of Theorem 4.1 is preserved for $G\setminus M_{\alpha,n-1}\in
M_{\alpha,n}$ by property (5) and Observation 5.1. Thus it is preserved for
$(G\setminus M_{\alpha,n-1})\cap M_{\alpha,n}=G_{\alpha,n}$ as well because of
Observation 5.2. Since $\left|E(G_{\alpha,n})\right|=\kappa_{\alpha}<\kappa$,
we can apply induction to obtain a perfect linkage in $G_{\alpha,n}$. ∎

Then $\mathcal{P}_{\alpha}:=\bigcup_{n<\omega}\mathcal{P}_{\alpha,n}$ is a
perfect linkage in $G\cap M_{\alpha}$. By property (3) and Fact 5.8 we know
that

$M_{\alpha+1,n},M_{\alpha+1,n-1}\in M_{\alpha,n+1}\subseteq M_{\alpha}.$

Therefore $G_{\alpha+1,n}\in M_{\alpha}$. Hence by Lemma 5.11 we can pick a
perfect linkage $\mathcal{P}_{\alpha+1,n}\in M_{\alpha}$ for $G_{\alpha+1,n}$.
But then we claim that
$\mathcal{Q}_{\alpha,n}:=\mathcal{P}_{\alpha+1,n}\setminus M_{\alpha}$ is a
perfect linkage in $G_{\alpha+1,n}\setminus
M_{\alpha}=G\cap(M_{\alpha+1,n}\setminus(M_{\alpha+1,n-1}\cup M_{\alpha}))$.
Indeed, if $e\in E(G_{\alpha+1,n})\setminus M_{\alpha}$ is incident with a
terminal vertex, then the unique $P_{e}\in\mathcal{P}_{\alpha+1,n}$ through
$e$ is not in $M_{\alpha}$ because $P_{e}$ is definable from
$e,\mathcal{P}_{\alpha+1,n}\in M_{\alpha}$, furthermore, $E(P)\cap
M_{\alpha}=\emptyset$ for similar reason. It follows, that
$\mathcal{Q}_{\alpha}:=\bigcup_{n<\omega}\mathcal{Q}_{\alpha,n}$ is a perfect
linkage in $G\cap(M_{\alpha+1}\setminus M_{\alpha})$. Since Lemma 5.10 ensures
that $G\cap M_{0}$ together with $G\cap(M_{\alpha+1}\setminus M_{\alpha})$ for
$\alpha<\mathsf{cf}(\kappa)$ forms an edge-partition of $G$, the path-system
$\mathcal{P}_{0}\cup\bigcup_{\alpha<\mathsf{cf}(\kappa)}\mathcal{Q}_{\alpha}$
is a perfect linkage in $G$.

##  6\. Proof of the countable case

It this section we prove the restriction of the Linkage theorem (Theorem 4.1)
to graphts with only countable many edges. First, we need some preparation.

######  Observation 6.1.

If $G=(V,E,I,T)$ is an inner Eulerian grapht and $H$ is either a cycle or a
$T$-path in $G$ then the grapht $G-E(H)$ is inner Eulerian.

###### Proof.

For a set $X\subseteq V\setminus T$ it is easy to see that
$\left|\delta_{G}(X)\cap E(H)\right|$ must be an even natural number. But then
if $d_{G-E(H)}(X)$ is finite, then
$d_{G-E(H)}(X)=d_{G}(X)-\left|\delta_{G}(X)\cap E(H)\right|$ holds, where both
quantities on the right side are even and therefore $d_{G-E(H)}(X)$ is also
even. ∎

######  Lemma 6.2.

Let $G=(V,E,I,\\{s,t\\})$ be an inner Eulerian grapht with
$\left|E\right|\leq\omega$ where $s$ is linked. Then there is a linkage
$\mathcal{P}$ for $s$ such that there is a family of pairwise edge-disjoint
cycles in $G-E(\mathcal{P})$ covering $\delta_{G-E(\mathcal{P})}(t)$.

###### Proof.

It is enough to show that for every $e\in\delta(s)\cup\delta(t)$ there is a
subgraph $H$ containing $e$, that is either an $st$-path or a cycle through
$t$ that does not contain $s$, such that $G-E(H)$ preserves the premise of
Lemma 6.2.

Being inner Eulerian is preserved “automatically” by Observation 6.1 thus we
only need to maintain the linkability of $s$. Let $\mathcal{P}$ be any linkage
of $s$. If $e\in E(\mathcal{P})$, then the unique $P_{e}\in\mathcal{P}$
through $e$ is suitable as $H$. Suppose that $e\notin E(\mathcal{P})$. Then
$e\notin\delta(s)$ (because $\mathcal{P}$ links $s$) and hence we must have
$e\in\delta(t)$. Let $\mathcal{A}$ be an edge-partition of $G$ into cycles and
$st$-paths (exists by Corollary 3.3) and let $H_{e}\in\mathcal{A}$ be the
unique element through $e$. If $E(H_{e})\cap E(\mathcal{P})=\emptyset$, then
$H:=H_{e}$ is suitable. Otherwise consider the orientation of $H_{e}$ where it
is a directed $ts$-path or a directed cycle in which $e$ is an outgoing edge
of $t$ . Let $v$ be the first vertex of $V(\mathcal{P})$ that we reach by
going along this orientation starting from $t$ (see Figure 3) and let $Q$ be
the corresponding segment of $H_{e}$ between $t$ and $v$. Take a path
$P\in\mathcal{P}$ witnessing $v\in V(\mathcal{P})$. Then the path $H:=sPvQ$ is
suitable because it does not share any edges with the paths in $\mathcal{P}-P$
and therefore the linkability of $s$ in $G-E(H)$ is witnessed by
$\mathcal{P}-P$.

$s$$t$$v$$Q$$P$$e$ Figure 3. The construction of $H$.

∎

######  Lemma 6.3.

Let $G=(V,E,I,\\{s,t\\})$ be an inner Eulerian grapht with
$\left|E\right|\leq\omega$ where $\delta(s)$ is the unique Erdős-Menger
$st$-cut. Then after the deletion of at most two edges, $s$ remains linked.

###### Proof.

Suppose for a contradiction that there are (not necessarily distinct) $f,g\in
E$ such that $s$ is not linked in $G-f-g$. We may assume that
$\delta_{G}(s)\cap\\{f,g\\}=\emptyset$ since otherwise the deletion of the
edge set $\\{f,g\\}\setminus\delta_{G}(s)$ already ruins the linkability of
$s$. We know that $s$ must remain linked in $G-f$ since otherwise by applying
Lemma 3.8 with $G$ and $f$ we obtain an Erdős-Menger $st$-cut that contains
$f$ and hence distinct from $\delta_{G}(s)$ contradicting the assumption that
$\delta_{G}(s)$ is the unique Erdős-Menger $st$-cut.

By the indirect assumption, $s$ is not linked in $G-f-g$ and we have just seen
that it is in $G-f$. Thus Lemma 3.8 can be applied with $G-f$ and $g$. This
provides a tight Erdős-Menger $st$-cut $C$ in $G-f$ that contains $g$. This
$C$ cannot be an Erdős-Menger $st$-cut in $G$ because $\delta(s)$ is the
unique one and $g\in C\setminus\delta(s)$. Therefore $f$ connects the two
sides of $C$, i.e. $C+f$ is an $st$-cut in $G$ (but not an Erdős-Menger
$st$-cut because $f\in(C+f)\setminus\delta(s)$). Contract the $t$-side of
$C+f$ to $t$ to obtain $G^{\prime}$. Note that $t$ is not linked in
$G^{\prime}$. The tightness of $C$ in $G-f$ ensures that $G^{\prime}$ with $s$
and $t$ satisfies the premise of Lemma 3.9. Therefore every linkage of $s$ in
$G^{\prime}$ misses exactly one edge from $\delta_{G^{\prime}}(t)$.

On the other hand, by Lemma 6.2 there exists a linkage $\mathcal{P}$ for $s$
in $G^{\prime}$ such that there is a family of pairwise edge-disjoint cycles
in $G^{\prime}-E(\mathcal{P})$ covering
$\delta_{G^{\prime}-E(\mathcal{P})}(t)$. Since a cycle through $t$ uses an
even number of edges incident with $t$, the set
$\delta_{G^{\prime}-E(\mathcal{P})}(t)$ cannot be a singleton. But then the
existence of this $\mathcal{P}$ contradicts the last sentence of the previous
paragraph. ∎

######  Corollary 6.4.

Let $G=(V,E,I,T)$ be an inner Eulerian grapht with $\left|E\right|\leq\omega$.
Then after the deletion of at most two edges all those $t\in T$ remains linked
for which $\delta(t)$ was the unique Erdős-Menger $t$-cut.

###### Proof.

For a given $t\in T$ we contract $T-t$ to a $t^{\prime}\in T-t$ and apply
Lemma 6.3. ∎

The restriction of the Linkage theorem (Theorem 4.1) to graphts with countably
many edges follows from the following lemma by a straightforward recursion:

######  Lemma 6.5.

Let $G=(V,E,I,T)$ be an inner Eulerian grapht with $\left|E\right|\leq\omega$
that satisfies the linkability condition. Then for every $e\in\bigcup_{t\in
T}\delta(t)$ there exists a $T$-path $P$ through $e$ such that the grapht
$G-E(P)$ is inner Eulerian and satisfies the linkability condition.

###### Proof.

By Observation 6.1, $G-E(P)$ is inner Eulerian for every $T$-path $P$, thus it
is enough to focus on the preservation of the linkability condition. Suppose
for a contradiction that the lemma is false. Observe that deletion of edges
with both end-vertex in $T$ does not ruin the linkability condition. Thus if
$G=(V,E,I,T)$ and $e_{0}\in\bigcup_{t\in T}\delta(t)$ form a counterexample,
then $e_{0}$ has only one of its endpoints, $s_{e_{0}}$ say, in $T$. We
associate the following quantity with counterexamples:

$\left|\left|(G,e_{0})\right|\right|:=\min\\{\left|E(P_{e_{0}})\right|:\
\mathcal{P}\text{ is a linkage of }s_{e_{0}},\ e_{0}\in E(P_{e_{0}}),\
P_{e_{0}}\in\mathcal{P}\\}.$

Let us fix a counterexample $(G,e_{0})$ that minimizes
$\left|\left|(G,e_{0})\right|\right|$ and write simply $s$ for $s_{e_{0}}$.
Let $\mathcal{P}=\\{P_{e}:\ e\in\delta_{G}(s)\\}$ be a path-system where the
minimum is taken where $e\in E(P_{e})$ for $e\in\delta_{G}(s)$.

######  Claim 6.6.

We can assume without loss of generality that for every $t\in T-s$:
$\delta_{G}(t)$ is the unique Erdős-Menger $t$-cut in $G$.

###### Proof.

We show that our original counterexample can be modified in order to satisfy
this additional property. Let $\mathcal{F}=\\{X_{t}:\ t\in T\\}$ be a family
that we obtain by applying Lemma 4.3 with $T^{\prime}=T-s$. Then (ii) of Lemma
4.3 ensures that $\delta_{G/\mathcal{F}}(t)$ is the unique Erdős-Menger
$t$-cut in $G/\mathcal{F}=:G^{\prime}$ for $t\in T^{\prime}$. For
$e\in\delta_{G}(s)=\delta_{G^{\prime}}(s)$, let $P^{\prime}_{e}$ be the
$T$-path in $G^{\prime}$ defined by the initial segment of $P_{e}$ from $s$
until its first common vertex with $\bigcup_{t\in T^{\prime}}X_{t}$ and let
$\mathcal{P}^{\prime}:=\\{P^{\prime}_{e}:\ e\in\delta_{G^{\prime}}(s)\\}$.
Obviously $\left|E(P^{\prime}_{e_{0}})\right|\leq\left|E(P_{e_{0}})\right|$,
thus if $G^{\prime}$ and $e_{0}$ form a counterexample, then it is also
minimizing in the sense that
$\left|\left|(G^{\prime},e_{0})\right|\right|=\left|\left|(G,e_{0})\right|\right|$.

Suppose for a contradiction that $(G^{\prime},e_{0})$ is not a counterexample
and let $Q_{e_{0}}$ be a $T$-path through $e_{0}$ such that
$G^{\prime}-E(Q_{e_{0}})$ satisfies the linkability condition. For $t\in
T^{\prime}$ let $\mathcal{P}_{t}=\\{P_{t,e}:\ e\in\delta_{G}(X_{t})\\}$ as in
(i) of Lemma 4.3. Denote $t_{0}$ the end-vertex of $Q_{e_{0}}$ distinct from
$s$ and let $f_{0}$ be the unique edge of $Q_{e_{0}}$ incident with $t_{0}$
(see Figure 4). Then $R_{e_{0}}:=sQ_{e_{0}}f_{0}P_{t_{0},f_{0}}t_{0}$ is a
$T$-path in $G$ covering $e_{0}$. Note that

$(G-E(R_{e_{0}}))/\mathcal{F}=G^{\prime}-E(Q_{e_{0}}).$

Let $\mathcal{P}^{\prime}_{s}$ consist of the single-edge paths corresponding
to $\delta_{G}(s)$,
$\mathcal{P}_{t_{0}}^{\prime}:=\mathcal{P}_{t_{0}}-P_{t_{0},f_{0}}$ and
$\mathcal{P}_{t}^{\prime}:=\mathcal{P}_{t}$ for $t\in T^{\prime}-t_{0}$. These
path-systems are as in the Lifting lemma (Observation 4.2) for $\mathcal{F}$
in $G-E(R_{e_{0}})$ including that $\mathcal{P}^{\prime}_{t}$ covers
$\delta_{G-E(R_{e_{0}})}(t)$ for $t\in T$. But then any linkage of a $t\in T$
in $G^{\prime}-E(Q_{e_{0}})$ can be lifted up to a linkage of $t$ in
$G-E(R_{e_{0}})$. Therefore $G-E(R_{e_{0}})$ satisfies the linkability
condition. This means that $R_{e_{0}}$ witnesses that $(G,e_{0})$ is not a
counterexample, a contradiction.

$s$$e_{0}$$Q_{e_{0}}$$t_{0}$$f_{0}$$t_{1}$$\mathcal{P}_{t_{1}}$$R_{e_{0}}$$P_{t_{0},f_{0}}$
Figure 4. The construction of $R_{e_{0}}$.

∎

Since only one endpoint of $e_{0}$ is in $T$, we have
$\left|E(P_{e_{0}})\right|\geq 2$. Let $f_{0}\in E(P_{e_{0}})$ be the edge
next to $e_{0}$ in $P_{e_{0}}$. We obtain $G^{\prime}$ from $G$ by deleting
the edges $e_{0}$ and $f_{0}$ and adding a single new edge $h_{0}$ connecting
$s$ and the end-vertex of $f_{0}$ that is not shared with $e_{0}$ (i.e. we
split off $e_{0}$ and $f_{0}$, a technique by Lovász from [29]). Let
$P_{h_{0}}$ be the path in $G^{\prime}$ with
$E(P_{h_{0}})=E(P_{e_{0}})-e_{0}-f_{0}+h_{0}$ and let us define
$\mathcal{P}^{\prime}:=\mathcal{P}-P_{e_{0}}+P_{h_{0}}$. For $X\subseteq
V\setminus T$, the quantities $d_{G}(X)$ and $d_{G^{\prime}}(X)$ are either
both infinite or they have the same parity, thus $G^{\prime}$ is also inner
Eulerian. The linkability condition for $s$ in $G^{\prime}$ is witnessed by
$\mathcal{P}^{\prime}$. Let $t\in T-s$ be arbitrary. The linkability condition
for $t$ holds in $G-e_{0}-f_{0}$ by Corollary 6.4 via Claim 6.6 and hence in
$G^{\prime}$ as well (if $h_{0}\in\delta_{G^{\prime}}(t)$, then $h_{0}$ is an
edge between $s$ and $t$ and hence a $T$-path itself). Note that $G^{\prime}$
and $h_{0}$ cannot form a counterexample for Lemma 6.5 because
$\left|\left|(G^{\prime},h_{0})\right|\right|=\left|\left|(G,e_{0})\right|\right|-1$
by $\left|E(P_{h_{0}})\right|=\left|E(P_{e_{0}})\right|-1$. Therefore we can
pick some $T$-path $P^{\prime}$ in $G^{\prime}$ through $h_{0}$ such that the
linkability condition holds in $G^{\prime}-E(P^{\prime})$. Let us take then a
$T$-path $P$ in $G$ through $e_{0}$ with $E(P)\subseteq
E(P^{\prime})-h_{0}+e_{0}+f_{0}$. Since $G^{\prime}-E(P^{\prime})$ is a
subgraph of $G-E(P)$ and
$\delta_{G-E(P)}(t)=\delta_{G^{\prime}-E(P^{\prime})}(t)$ holds for $t\in T$,
the linkability condition in $G^{\prime}-E(P^{\prime})$ implies the
linkability condition in $G-E(P)$. This contradicts the fact that $G$ and
$e_{0}$ form a counterexample to Lemma 6.5. ∎

##  7\. Outlook

The minimax theorems due to Gallai and Mader (independently) about packing
edge-disjoint, vertex-disjoint and internally vertex-disjoint $T$-paths in
arbitrary finite graphs [30, 22, 31] provide a promising material for
structural infinite generalizations. Our corresponding conjectures have
already been discussed in the last section of [28].

Let us formulate the following (somewhat vague) meta-conjecture:

######  Conjecture 7.1.

Theorems that can be proved by augmenting paths for finite structures remain
true structurally (possibly under some restrictions) for infinite ones.

The infinite generalization of: Menger’s theorem [5], Ford-Fulkerson theorem
[7], Tutte’s matching theorem [4] (together with the Gallai-Edmonds structure
theorem [11, Theorem 3.1]), Edmonds’ matroid intersection theorem [26] 444The
maxflow-mincut theorem of Ford and Fulkerson and Edmonds’ matroid intersection
theorem are extended only to countable structures for now. and the Lovász-
Cherkassky theorem (Theorem 1.2) are special instances of Conjecture 7.1 and
they do not require any restrictions. Dilworth’ theorem [20] states that every
finite poset admits a partition $\mathcal{P}$ into chains such that there is
an antichain $A$ with $A\cap C\neq\emptyset$ for every $C\in\mathcal{P}$. It
is not too hard to construct an infinite poset that cannot be partitioned into
finitely many chains (because admitting arbitrary large finite antichains) but
does not even contain an infinite antichain. Indeed,

$P:=\\{(m,n)\in\mathbb{N}\times\mathbb{N}:\ n\leq m\\}$

where $(m,n)\leq(m^{\prime},n^{\prime})$ iff $m\leq m^{\prime}$ has this
property. However, Dilworth’ theorem holds for posets without infinite chains
[2, Theorem 7.1] (for countable posets, excluding only more specific
substructures is already sufficient [6]). Since Dilworth’ theorem admits an
augmenting path based proof, it fits under the umbrella of Conjecture 7.1 with
the restriction that we forbid infinite chains. Based on a theorem of Gallai
and Milgram [23], we conjecture the following generalization:

######  Conjecture 7.2 (infinite Gallai-Milgram).

Every digraph $D$ without infinite directed paths admits a vertex-partition
$\mathcal{P}$ into directed paths and an independent set $U$ of vertices such
that $U$ meets every $P\in\mathcal{P}$.

The restriction of Conjecture 7.2 to acyclic digraphs follows from the
infinite version of König’s theorem [3] the same way the infinite Dilworth’
theorem does555This was observed by Aharoni (personal communication). (see the
proof of [2, Theorem 7.1]).

Introducing new specific conjectures based on Conjecture 7.1 is quite easy but
proving them is usually a highly non-trivial task. Let us mention a second
example based on [21, Theorem 2]:

######  Conjecture 7.3 (infinite Frank-Sebő-Tardos).

Let $G=(S,T,E)$ be a (possibly infinite) $2$-edge-connected bipartite graph.
Then there is a strong orientation $D$ of $G$ and a partition $\mathcal{P}$ of
$T$ such that for every $U\in\mathcal{P}$, each weak component of $D-U$ sends
only one directed edge toward $U$.

## References

  * [1] Seyed Hadi Afzali Borujeni, Hiu-Fai Law and Malte Müller  “Infinite Gammoids: Minors and Duality”  In _The Electronic Journal of Combinatorics_ 22.4, 2015, pp. P4–37  DOI: 10.37236/5107
  * [2] Ron Aharoni  “Infinite matching theory”  In _Discrete mathematics_ 95.1-3 Elsevier, 1991, pp. 5–22  DOI: 10.1016/0012-365x(91)90327-x
  * [3] Ron Aharoni  “König’s duality theorem for infinite bipartite graphs”  In _Journal of the London Mathematical Society_ 2.1 Wiley Online Library, 1984, pp. 1–12  DOI: 10.1112/jlms/s2-29.1.1
  * [4] Ron Aharoni  “Matchings in infinite graphs”  In _Journal of Combinatorial Theory, Series B_ 44.1 Elsevier, 1988, pp. 87–125  DOI: 10.1016/0095-8956(88)90098-6
  * [5] Ron Aharoni and Eli Berger  “Menger’s theorem for infinite graphs”  In _Inventiones mathematicae_ 176.1 Springer, 2009, pp. 1–62  DOI: 10.1007/s00222-008-0157-3
  * [6] Ron Aharoni and Eli Berger  “Strongly maximal antichains in posets”  In _Discrete mathematics_ 311.15 Elsevier, 2011, pp. 1518–1522  DOI: 10.1016/j.disc.2010.12.023
  * [7] Ron Aharoni, Eli Berger, Agelos Georgakopoulos, Amitai Perlstein and Philipp Sprüssel  “The max-flow min-cut theorem for countable networks”  In _Journal of Combinatorial Theory, Series B_ 101.1 Elsevier, 2011, pp. 1–17  DOI: 10.1007/springerreference_5803
  * [8] Ron Aharoni and Martin Loebl  “Strongly perfect infinite graphs”  In _Israel Journal of Mathematics_ 90.1-3 Springer, 1995, pp. 81–91  DOI: 10.1007/BF02783207
  * [9] Ron Aharoni, Crispin Nash-Williams and Saharon Shelah  “A general criterion for the existence of transversals”  In _Proceedings of the London Mathematical Society_ 3.1 Narnia, 1983, pp. 43–68  DOI: 10.1112/plms/s3-47.1.43
  * [10] Ron Aharoni, Crispin Nash-Williams and Saharon Shelah  “Another Form of a Criterion for the Existence of Transversals”  In _Journal of the London Mathematical Society_ 2.2 Wiley Online Library, 1984, pp. 193–203  DOI: 10.1112/plms/s3-47.1.43
  * [11] Ron Aharoni and Ran Ziv  “LP duality in infinite hypergraphs”  In _Journal of Combinatorial Theory, Series B_ 50.1 Elsevier, 1990, pp. 82–92  DOI: 10.1016/0095-8956(90)90098-k
  * [12] Ron Aharoni and Ran Ziv  “The intersection of two infinite matroids”  In _Journal of the London Mathematical Society_ 58.03 Cambridge Univ Press, 1998, pp. 513–525  DOI: 10.1112/s0024610798006723
  * [13] Elad Aigner-Horev, Johannes Carmesin and Jan-Oliver Fröhlich  “On the intersection of infinite matroids”  In _Discrete Mathematics_ 341.6 Elsevier, 2018, pp. 1582–1596  DOI: 10.1016/j.disc.2018.02.018
  * [14] Amena Assem, Marcel Koloschin and Max Pitz  “The Nash-Williams orientation theorem for graphs with countably many ends”, 2023  arXiv:2310.03601
  * [15] Thomas Böhme, Frank Göring and Jochen Harant  “Menger’s theorem”  In _Journal of Graph Theory_ 37.1 Wiley Online Library, 2001, pp. 35–36  DOI: 10.1002/jgt.1001
  * [16] Nathan Bowler and Johannes Carmesin  “On the intersection conjecture for infinite trees of matroids”  In _Journal of Combinatorial Theory, Series B_ 151, 2021, pp. 46–82  DOI: 10.1016/j.jctb.2021.05.007
  * [17] Johannes Carmesin  “Topological infinite gammoids, and a new Menger-type theorem for infinite graphs”  In _Electronic Journal of Combinatorics_ 25.P3.38, 2018  DOI: 10.37236/6083
  * [18] Boris V. Cherkassky  “A solution of a problem on multicommodity flows in a network” (in Russian)  In _Ekonomika i Matematicheskie Metody_ 13.1, 1977, pp. 143–151
  * [19] Reinhard Diestel and Carsten Thomassen  “A Cantor-Bernstein theorem for paths in graphs”  In _The American Mathematical Monthly_ 113.2 Taylor & Francis, 2006, pp. 161–166  DOI: 10.2307/27641867
  * [20] Robert Palmer Dilworth  “A decomposition theorem for partially ordered sets”  In _Classic papers in combinatorics_ Springer, 1987, pp. 139–144
  * [21] András Frank, Éva Tardos and András Sebő  “Covering directed and odd cuts”  In _Mathematical Programming at Oberwolfach II_ Springer, 1984, pp. 99–112  DOI: 10.1007/bfb0121011
  * [22] Tibor Gallai  “Maximum-minimum Sätze und verallgemeinerte Faktoren von Graphen”  In _Acta Mathematica Academiae Scientiarum Hungarica_ 12.1-2 Springer, 1964, pp. 131–173  DOI: 10.1007/bf02066678
  * [23] Tilbor Gallai and Arthur Norton Milgram  “Verallgemeinerung eines graphentheoretischen Satzes von Rédei”  In _Acta Sc. Math_ 21, 1960, pp. 181–186
  * [24] Satoru Iwata and Yu Yokoi  “A blossom algorithm for maximum edge-disjoint T-paths”  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2020, pp. 1933–1944  SIAM  DOI: 10.1137/1.9781611975994.119
  * [25] Thomas Jech  “Set theory, 3rd Millennium ed”  In _Springer Monographs in Mathematics, Springer_ , 2002
  * [26] Attila Joó  “Proof of Nash-Williams’ intersection conjecture for countable matroids”  In _Advances in Mathematics_ 380, 2021, pp. 107608  DOI: 10.1016/j.aim.2021.107608
  * [27] Attila Joó  “The complete lattice of Erdős-Menger separations”, 2019  arXiv:1904.06244 [math.CO]
  * [28] Attila Joó  “The Lovász-Cherkassky theorem in countable graphs”  In _Journal of Combinatorial Theory, Series B_ 159, 2023, pp. 1–19  DOI: https://doi.org/10.1016/j.jctb.2022.11.001
  * [29] László Lovász  “On some connectivity properties of Eulerian graphs”  In _Acta Mathematica Academiae Scientiarum Hungarica_ 28.1-2 Springer, 1976, pp. 129–138  DOI: 10.1007/bf01902503
  * [30] Wolfgang Mader  “Über die Maximalzahl kantendisjunkter A-Wege”  In _Archiv der Mathematik_ 30.1 Springer, 1978, pp. 325–336  DOI: 10.1007/bf01226062
  * [31] Wolfgang Mader  “Über die Maximalzahl kreuzungsfreier H-Wege”  In _Archiv der Mathematik_ 31.1 Springer, 1978, pp. 387–402  DOI: 10.1007/bf01226465
  * [32] C…. Nash-Williams  “Decomposition of graphs into closed and endless chains”  In _Proceedings of the London Mathematical Society_ 3.1 Oxford University Press, 1960, pp. 221–238  DOI: 10.1112/plms/s3-10.1.221
  * [33] Klaus-Peter Podewski and Karsten Steffens  “Injective choice functions for countable families”  In _Journal of Combinatorial Theory, Series B_ 21.1 Elsevier, 1976, pp. 40–46  DOI: 10.1016/0095-8956(76)90025-3
  * [34] Lajos Soukup  “Elementary submodels in infinite combinatorics”  In _Discrete Mathematics_ 311.15 Elsevier, 2011, pp. 1585–1598  DOI: 10.1016/j.disc.2011.01.025
  * [35] Karsten Steffens  “Matchings in countable graphs”  In _Canadian Journal of Mathematics_ 29.1 Cambridge University Press, 1977, pp. 165–168  DOI: 10.4153/cjm-1977-016-8
  * [36] Carsten Thomassen  “Orientations of infinite graphs with prescribed edge-connectivity”  In _Combinatorica_ 36.5 Springer, 2016, pp. 601–621  DOI: 10.1007/s00493-015-3173-0