\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{amsfonts}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, November 16, 2018 18:25:06}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand{\of}{\text{ of }}
\ihead{Notes on network flows}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\title{Notes on network flows}
\author{Darij Grinberg}
\date{draft,
%TCIMACRO{\TeXButton{TeX field}{\today}}%
%BeginExpansion
\today
%EndExpansion
}
\maketitle
\tableofcontents
\section{Introduction}
\subsection{What is this?}
In these notes, we will explain the basics of the theory of network flows. We
will barely scratch the surface; for a more comprehensive survey, see
Schrijver's \cite[Chapter 4]{Schrij17}. Also, \cite[\S 8.2]{Martin17} gives a
neat introduction, and \cite{ForFul62} is the classical text on the subject.
The thesis \cite{Thalwi08} appears to be a thorough treatment of the subject
with lots of technical details. See also the \textquotedblleft Lecture notes
on maximum flows and minimum cut problems\textquotedblright\ in
\cite{Goeman17}.
We shall mostly follow \cite[\S 8.2]{Martin17}. In particular, we will only
use elementary methods. More advanced disciplines (such as linear optimization
and polyhedral geometry) offer alternative points of view on the theory of
network flows; we shall ignore these. We shall also ignore real-life
applications, although there are many (see \cite[Chapter 4]{Schrij17} for a
few, and see \cite[\S 2]{Schrij12} for the Cold War origins of the subject).
These notes have been written for undergraduate classes on graph theory and
combinatorics. They are derivative of the notes \cite{lec16}, but are more
self-contained than \cite{lec16} and are concerned with a more general setting.
\subsection{Notations}
We let $\mathbb{N}$ denote the set $\left\{ 0,1,2,\ldots\right\} $ of all
nonnegative integers.
We let $\mathbb{Q}_{+}$ denote the set $\left\{ x\in\mathbb{Q}\mid
x\geq0\right\} $ of all nonnegative rational numbers.
We let $\mathbb{R}_{+}$ denote the set $\left\{ x\in\mathbb{R}\mid
x\geq0\right\} $ of all nonnegative real numbers.
\subsection{Simple digraphs and multidigraphs}
The theory of network flows can be built either on the notion of a
\textit{simple digraph}, or on the (somewhat more general) notion of a
\textit{multidigraph}. We shall take the latter choice (thus obtaining a
slightly more general theory), but we will define both simple digraphs and multidigraphs.
First, let us define simple digraphs, since these are the simpler object:
\begin{definition}
A \textit{simple digraph} is defined to be a pair $\left( V,A\right) $
consisting of a finite set $V$ and of a subset $A$ of $V\times V$. The
elements of $V$ are called the \textit{vertices} of this simple digraph; the
elements of $A$ are called its \textit{arcs}. If $a=\left( u,v\right) $ is
an arc of a simple digraph $\left( V,A\right) $, then $u$ is called the
\textit{source} of this arc $a$, and $v$ is called the \textit{target} of this
arc $a$.
\end{definition}
\begin{example}
\label{exa.digraph.1}\textbf{(a)} The pair%
\[
\left( \left\{ 1,2,3\right\} ,\left\{ \left( 1,2\right) ,\left(
2,3\right) ,\left( 1,3\right) \right\} \right)
\]
is a simple digraph. Its vertices are $1,2,3$. Its arcs are $\left(
1,2\right) $, $\left( 2,3\right) $ and $\left( 1,3\right) $. The arc
$\left( 2,3\right) $ has source $2$ and target $3$.
\textbf{(b)} The pair
\[
\left( \left\{ 1,3,5\right\} ,\left\{ \left( 1,5\right) ,\left(
5,5\right) \right\} \right)
\]
is a simple digraph. Its vertices are $1,3,5$. Its arcs are $\left(
1,5\right) $ and $\left( 5,5\right) $.
\end{example}
A simple digraph $\left( V,A\right) $ can be visually represented as follows:
\begin{itemize}
\item For each vertex $v\in V$, choose a point in the plane and label it with
a \textquotedblleft$v$\textquotedblright.
\item For each arc $\left( u,v\right) \in A$, draw an arrow from the point
labelled \textquotedblleft$u$\textquotedblright\ to the point labelled
\textquotedblleft$v$\textquotedblright. (The arrow can be straight or curved.)
\end{itemize}
(Of course, the drawing should be made with readability in mind: The points
labelled by the vertices should be chosen sufficiently far apart that the
labels don't overlap. The arrows are allowed to cross\footnote{In fact, this
is unavoidable for certain digraphs.}, but they should cross in such a way
that it is clear which arrow goes where. In short, the representation should
unambiguously determine the digraph.)
There are many ways to represent a given digraph.
\begin{example}
\textbf{(a)} The digraph $\left( \left\{ 1,2,3\right\} ,\left\{ \left(
1,2\right) ,\left( 2,3\right) ,\left( 1,3\right) \right\} \right) $
from Example \ref{exa.digraph.1} \textbf{(a)} can be represented as follows:%
\[%
%TCIMACRO{\TeXButton{digraph on 1,2,3}{\xymatrix{
%& 2 \ar[dr] \\
%1 \ar[ur] \ar[rr] & & 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \ar[dr] \\
1 \ar[ur] \ar[rr] & & 3
}%
%EndExpansion
.
\]
It can also be represented as follows:%
\[%
%TCIMACRO{\TeXButton{digraph on 1,2,3}{\xymatrix{
%1 \ar@/^/[rr] \ar[rd] & & 2 \ar[ld] \\
%& 3
%}}}%
%BeginExpansion
\xymatrix{
1 \ar@/^/[rr] \ar[rd] & & 2 \ar[ld] \\
& 3
}%
%EndExpansion
.
\]
\textbf{(b)} The digraph $\left( \left\{ 1,3,5\right\} ,\left\{ \left(
1,5\right) ,\left( 5,5\right) \right\} \right) $ from Example
\ref{exa.digraph.1} \textbf{(b)} can be represented as follows:%
\[%
%TCIMACRO{\TeXButton{digraph on 1,3,5}{\xymatrix{
%1 \ar[r] & 5 \ar@(ul,ur) & 3
%}}}%
%BeginExpansion
\xymatrix{
1 \ar[r] & 5 \ar@(ul,ur) & 3
}%
%EndExpansion
.
\]
\end{example}
Note that an arc of a simple digraph is uniquely determined by its source and
its target: indeed, it is the pair consisting of its source and its target.
Multidigraphs are similar to simple digraphs, except that this is no longer
true: their arcs are not uniquely determined by their sources and their
targets any more, but rather have \textquotedblleft their own
identities\textquotedblright. Here is how multidigraphs are defined:
\begin{definition}
A \textit{multidigraph} is a triple $\left( V,A,\phi\right) $, where $V$ and
$A$ are finite sets and where $\phi$ is a map from $A$ to $V\times V$. The
elements of $V$ are called the \textit{vertices} of this multidigraph; the
elements of $A$ are called its \textit{arcs}. If $a$ is an arc of a
multidigraph $\left( V,A,\phi\right) $, and if $\left( u,v\right)
=\phi\left( a\right) $, then $u$ is called the \textit{source} of this arc
$a$, and $w$ is called the \textit{target} of this arc $a$.
\end{definition}
\begin{example}
\label{exa.multidigraph.1}\textbf{(a)} Let $\alpha,\beta,\gamma,\delta$ be any
four distinct objects (it doesn't matter which objects we take; for example,
$10,11,12,13$ do the job). Let $V$ be the set $\left\{ 1,2,3\right\} $, and
let $A$ be the set $\left\{ \alpha,\beta,\gamma,\delta\right\} $. Let
$\phi:A\rightarrow V\times V$ be the map given by%
\begin{align*}
\phi\left( \alpha\right) & =\left( 1,3\right) ,\ \ \ \ \ \ \ \ \ \ \phi
\left( \beta\right) =\left( 2,3\right) ,\\
\phi\left( \gamma\right) & =\left( 1,3\right) ,\ \ \ \ \ \ \ \ \ \ \phi
\left( \delta\right) =\left( 2,1\right) .
\end{align*}
Then, the triple $\left( V,A,\phi\right) $ is a multidigraph. Its vertices
are $1,2,3$; its arcs are $\alpha,\beta,\gamma,\delta$. The arc $\alpha$ has
source $1$ and target $3$; so does the arc $\gamma$.
\textbf{(b)} Let $V$ and $A$ be as in part \textbf{(a)}. But now, let
$\phi:A\rightarrow V\times V$ be the map given by%
\begin{align*}
\phi\left( \alpha\right) & =\left( 1,1\right) ,\ \ \ \ \ \ \ \ \ \ \phi
\left( \beta\right) =\left( 1,2\right) ,\\
\phi\left( \gamma\right) & =\left( 2,2\right) ,\ \ \ \ \ \ \ \ \ \ \phi
\left( \delta\right) =\left( 1,2\right) .
\end{align*}
Then, the triple $\left( V,A,\phi\right) $ is a multidigraph as well.
\end{example}
A multidigraph $\left( V,A,\phi\right) $ is visually represented in the same
way as a simple digraph $\left( V,A\right) $, with one difference: An arc
$a\in A$ is now drawn as an arrow from the point labelled by its source to the
point labelled by its target, and we furthermore label this arrow with an
\textquotedblleft$a$\textquotedblright.
\begin{example}
\textbf{(a)} The multidigraph $\left( V,A,\phi\right) $ from Example
\ref{exa.multidigraph.1} \textbf{(a)} can be represented as follows:%
\[%
%TCIMACRO{\TeXButton{multidigraph (a)}{\xymatrix{
%& 2 \ar[dl]_{\delta} \ar[dd]^{\beta} \\
%1 \ar[rd]_{\gamma} \ar@/_3pc/[rd]_{\alpha} \\
%& 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \ar[dl]_{\delta} \ar[dd]^{\beta} \\
1 \ar[rd]_{\gamma} \ar@/_3pc/[rd]_{\alpha} \\
& 3
}%
%EndExpansion
.
\]
\textbf{(b)} The multidigraph $\left( V,A,\phi\right) $ from Example
\ref{exa.multidigraph.1} \textbf{(b)} can be represented as follows:%
\[%
%TCIMACRO{\TeXButton{multidigraph (b)}{\xymatrix{
%1 \ar@(ul,ur)^{\alpha} \ar@/^/[rr]^{\beta} \ar@/_/[rr]_{\delta} & & 2 \ar@
%(ul,ur)^{\gamma} & & 3
%}}}%
%BeginExpansion
\xymatrix{
1 \ar@(ul,ur)^{\alpha} \ar@/^/[rr]^{\beta} \ar@/_/[rr]_{\delta} & & 2 \ar@
(ul,ur)^{\gamma} & & 3
}%
%EndExpansion
.
\]
\end{example}
Let us summarize the difference between a simple digraph and a multidigraph:
An arc of a simple digraph $\left( V,A\right) $ is merely a pair consisting
of its source and its target, whereas an arc of a multidigraph $\left(
V,A,\phi\right) $ can be an arbitrary object (so it \textquotedblleft has its
own identity\textquotedblright) whose source and target are assigned to it by
the map $\phi$. Thus, we can regard multidigraphs as a refined version of
simple digraphs. Every simple digraph gives rise to a multidigraph as follows:
\begin{definition}
Let $\left( V,A\right) $ be a simple digraph. Let $\iota:A\rightarrow
V\times V$ be the inclusion map (i.e., the map that sends each $a\in A$ to $a$
itself); this is well-defined because $A$ is a subset of $V\times V$ (since
$\left( V,A\right) $ is a simple digraph). Then, $\left( V,A,\iota\right)
$ is a multidigraph. This multidigraph $\left( V,A,\iota\right) $ is called
the \textit{multidigraph induced by }$\left( V,A\right) $; we will often
just identify it with the simple digraph $\left( V,A\right) $ (so that each
simple digraph becomes a multidigraph in this way).
\end{definition}
\begin{example}
The simple digraph
\[%
%TCIMACRO{\TeXButton{digraph on 1,2,3}{\xymatrix{
%& 2 \ar[dr] \\
%1 \ar[ur] \ar[rr] & & 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \ar[dr] \\
1 \ar[ur] \ar[rr] & & 3
}%
%EndExpansion
\]
becomes identified with the multidigraph%
\[%
%TCIMACRO{\TeXButton{multidigraph on 1,2,3}{\xymatrix{
%& 2 \ar[dr]^{\tup{2,3}} \\
%1 \ar[ur]^{\tup{1,2}} \ar[rr]_{\tup{1,3}} & & 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \ar[dr]^{\tup{2,3}} \\
1 \ar[ur]^{\tup{1,2}} \ar[rr]_{\tup{1,3}} & & 3
}%
%EndExpansion
\]
in this way.
\end{example}
Both simple digraphs and multidigraphs are subsumed under the concept of a
\textit{digraph}, which is an abbreviation for \textquotedblleft directed
graph\textquotedblright.
\subsection{Walks and paths}
Two of the fundamental concepts regarding multidigraphs is that of a walk and
that of a path. Let us define them:
\begin{definition}
Let $D=\left( V,A,\phi\right) $ be a multidigraph.
\textbf{(a)} A \textit{walk} in $D$ is defined to be a list of the form
$\left( v_{0},a_{1},v_{1},a_{2},v_{2},\ldots,a_{k},v_{k}\right) $, where
$v_{0},v_{1},\ldots,v_{k}$ are vertices of $D$, and where $a_{i}$ is an arc of
$D$ having source $v_{i-1}$ and target $v_{i}$ for each $i\in\left\{
1,2,\ldots,k\right\} $. (Note that $k=0$ is allowed; in this case, the walk
is a $1$-tuple $\left( v_{0}\right) $ consisting of a single vertex $v_{0}$.)
\textbf{(b)} Consider any walk $\left( v_{0},a_{1},v_{1},a_{2},v_{2}%
,\ldots,a_{k},v_{k}\right) $ in $D$. The \textit{vertices} of this walk are
defined to be $v_{0},v_{1},\ldots,v_{k}$. Moreover, $v_{0}$ is called the
\textit{starting point} of the walk, and $v_{k}$ is called the \textit{ending
point} of the walk. The \textit{arcs} of this walk are defined to be
$a_{1},a_{2},\ldots,a_{k}$. The \textit{length} of this walk is defined to be
$k$.
\textbf{(c)} A walk is said to be a \textit{path} if its vertices are
distinct. (In other words, a walk $\left( v_{0},a_{1},v_{1},a_{2}%
,v_{2},\ldots,a_{k},v_{k}\right) $ is a path if and only if $v_{0}%
,v_{1},\ldots,v_{k}$ are distinct.)
\textbf{(d)} Let $s$ and $t$ be two vertices of $D$. A \textit{walk from }$s$
\textit{to }$t$ in $D$ means a walk $\left( v_{0},a_{1},v_{1},a_{2}%
,v_{2},\ldots,a_{k},v_{k}\right) $ in $D$ such that $v_{0}=s$ and $v_{k}=t$.
Likewise, a \textit{path from }$s$ \textit{to }$t$ in $D$ means a path
$\left( v_{0},a_{1},v_{1},a_{2},v_{2},\ldots,a_{k},v_{k}\right) $ in $D$
such that $v_{0}=s$ and $v_{k}=t$.
\end{definition}
\begin{example}
\textbf{(a)} Let $D$ be the multidigraph $\left( V,A,\phi\right) $ from
Example \ref{exa.multidigraph.1} \textbf{(a)}. Then,%
\[
\left( 1\right) ,\ \ \ \ \ \ \ \ \ \ \left( 1,\gamma,3\right)
,\ \ \ \ \ \ \ \ \ \ \left( 1,\delta,3\right) ,\ \ \ \ \ \ \ \ \ \ \left(
2\right) \ \ \ \ \ \ \ \ \ \ \text{and }\left( 2,\delta,1,\alpha,3\right)
\]
are five distinct walks in $D$. All of them are also paths in $D$. The lengths
of these walks are $0,1,1,0,2$, respectively. The fifth of these walks is a
walk from $2$ to $3$ (and also a path from $2$ to $3$). The vertices of the
third walk are $1$ and $3$.
\textbf{(b)} Now, let $D$ be the multidigraph $\left( V,A,\phi\right) $ from
Example \ref{exa.multidigraph.1} \textbf{(b)} instead. Then,%
\[
\left( 1\right) ,\ \ \ \ \ \ \ \ \ \ \left( 1,\alpha,1\right)
,\ \ \ \ \ \ \ \ \ \ \left( 1,\beta,2\right) ,\ \ \ \ \ \ \ \ \ \ \left(
2,\gamma,2\right) ,\ \ \ \ \ \ \ \ \ \ \text{and }\left( 3\right)
\]
are five distinct walks in $D$. The first, third and fifth of these walks are
paths in $D$; the other two are not. The lengths of these five walks are
$0,1,1,1,0$, respectively. The fifth of these walks is a walk from $3$ to $3$
(and also a path from $3$ to $3$). The vertices of the second walk are $1$ and
$1$.
\textbf{(c)} Now, let $D$ be the multidigraph%
\[%
%TCIMACRO{\TeXButton{a directed 3-cycle}{\xymatrix{
%1 \ar[rr]^{\alpha} & & 2 \ar[ld]^{\beta} \\
%& 3 \ar[ul]^{\gamma}
%}}}%
%BeginExpansion
\xymatrix{
1 \ar[rr]^{\alpha} & & 2 \ar[ld]^{\beta} \\
& 3 \ar[ul]^{\gamma}
}%
%EndExpansion
.
\]
Then, $\left( 1,\alpha,2,\beta,3,\gamma,1\right) $ is a walk from $1$ to
$1$, but not a path (since its vertices $1,2,3,1$ are not distinct).
\end{example}
One of the most fundamental facts about walks in a multidigraph is the following:
\begin{proposition}
\label{prop.multidigraph.walk-to-path}Let $D$ be a multidigraph. Let $s$ and
$t$ be two vertices of $D$. Assume that there exists a walk from $s$ to $t$ in
$D$. Then, there exists a path from $s$ to $t$ in $D$.
\end{proposition}
\begin{example}
Let $D$ be the multidigraph%
\[%
%TCIMACRO{\TeXButton{complicated walk}{\xymatrix{
%& & 5 \ar[d]^{\gamma} \\
%1 \ar[r]^{\alpha} & 2 \ar[ru]^{\beta} \ar[r]^{\lambda} & 3 \ar[d]^{\delta}
%\ar[r]^{\mu} & 6 \\
%& & 4 \ar[ul]^{\varepsilon}
%}}}%
%BeginExpansion
\xymatrix{
& & 5 \ar[d]^{\gamma} \\
1 \ar[r]^{\alpha} & 2 \ar[ru]^{\beta} \ar[r]^{\lambda} & 3 \ar[d]^{\delta}
\ar[r]^{\mu} & 6 \\
& & 4 \ar[ul]^{\varepsilon}
}%
%EndExpansion
.
\]
Then, $\left( 1,\alpha,2,\beta,5,\gamma,3,\delta,4,\varepsilon,2,\lambda
,3,\mu,6\right) $ is a walk from $1$ to $6$ in $D$, but not a path. Thus,
Proposition \ref{prop.multidigraph.walk-to-path} (applied to $s=1$ and $t=6$)
yields that there exists a path from $1$ to $6$ in $D$. And indeed, $\left(
1,\alpha,2,\lambda,3,\mu,6\right) $ is such a path. (It is not the only path;
another is $\left( 1,\alpha,2,\beta,5,\gamma,3,\mu,6\right) $.)
\end{example}
\begin{proof}
[Proof of Proposition \ref{prop.multidigraph.walk-to-path} (sketched).]We
claim the following:
\begin{statement}
\textit{Claim 1:} Let $\mathbf{w}$ be a walk from $s$ to $t$ in $D$. Then,
there exists a path from $s$ to $t$ in $D$.
\end{statement}
[\textit{Proof of Claim 1:} We shall prove Claim 1 by strong induction on the
length of $\mathbf{w}$. Thus, we fix a $k\in\mathbb{N}$, and we assume that
Claim 1 holds for all walks $\mathbf{w}$ having length $}[dr]_{\beta: 1} & \boxed{3} \ar@
%{=>}[r]^{\gamma: 1}
%\ar[dr]_{\delta: 2} & 2 \ar[r]^{\mu: 2} & 5 \ar[dl]_{\nu: 1} \ar[dr]^{\pi: 2}
%\\
%& 7 \ar[r]_{\varepsilon: 3} & \boxed{4} \ar@{=>}[u]^{\lambda: 1} \ar@
%{=>}[r]_{\kappa: 1} & 6 \ar[r]_{\sigma: 1} & 8 = t
%}}}%
%BeginExpansion
\xymatrix@C=7pc@R=5pc{
\boxed{s = 1} \ar[r]^{\alpha: 2} \ar@{=>}[dr]_{\beta: 1} & \boxed{3} \ar@
{=>}[r]^{\gamma: 1}
\ar[dr]_{\delta: 2} & 2 \ar[r]^{\mu: 2} & 5 \ar[dl]_{\nu: 1} \ar[dr]^{\pi: 2}
\\
& 7 \ar[r]_{\varepsilon: 3} & \boxed{4} \ar@{=>}[u]^{\lambda: 1} \ar@
{=>}[r]_{\kappa: 1} & 6 \ar[r]_{\sigma: 1} & 8 = t
}%
%EndExpansion
\]
(where the vertices in $\left\{ 1,3,4\right\} $ have been marked by boxes).
Notice that every network $N$ (with notations as in Definition
\ref{def.network.notations}) has two special cuts: the first is the cut
\[
\left[ \left\{ s\right\} ,\overline{\left\{ s\right\} }\right] =\left\{
a\in A\ \mid\ \text{the source of }a\text{ is }s\text{, but the target is
not}\right\}
\]
corresponding to the $s$-$t$-cutting subset $\left\{ s\right\} $; the second
is the cut%
\[
\left[ \overline{\left\{ t\right\} },\left\{ t\right\} \right] =\left\{
a\in A\ \mid\ \text{the target of }a\text{ is }t\text{, but the source is
not}\right\}
\]
corresponding to the $s$-$t$-cutting subset $\overline{\left\{ t\right\} }$.
\subsection{The max-flow-min-cut theorems}
Proposition \ref{prop.2} \textbf{(c)} thus says that the value of a flow is
always $\leq$ to the capacity of a cut. But can we achieve equality?
One of the most important results in combinatorics -- the
\textit{max-flow-min-cut theorem} -- says that \textquotedblleft
yes\textquotedblright: In each network, we can find a flow and a cut such that
the value of the flow equals the capacity of the cut. More precisely, there
are three \textquotedblleft max-flow-min-cut theorems\textquotedblright,
corresponding to different kinds of flows. The first one is about the kind of
flows we have defined above:
\begin{theorem}
\label{thm.3a}Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}. Then,%
\begin{equation}
\max\left\{ \left\vert f\right\vert \ \mid\ f\text{ is a flow}\right\}
=\min\left\{ c\left( S,\overline{S}\right) \ \mid\ S\subseteq V;\ s\in
S;\ t\notin S\right\} . \label{eq.thm.3a.1}%
\end{equation}
In particular, the left-hand side of this equation is well-defined (i.e.,
there exists a flow $f$ for which $\left\vert f\right\vert $ is maximum). (Of
course, the right-hand side of (\ref{eq.thm.3a.1}) is well-defined, because
there are only finitely many subsets $S$ of $V$ satisfying $s\in S$ and
$t\notin S$, and because there exists at least one such subset)
\end{theorem}
The equality (\ref{eq.thm.3a.1}) in Theorem \ref{thm.3a} says that the maximum
value of a flow equals the minimum value of $c\left( S,\overline{S}\right) $
where $S$ ranges over the $s$-$t$-cutting subsets of $V$. In other words, the
maximum value of a flow equals the minimum capacity of a cut.
Another variant of the max-flow-min-cut theorem makes the same claim about
\textit{integer flows} -- i.e., flows $f:A\rightarrow\mathbb{Q}_{+}$ such that
every arc $a\in A$ satisfies $f\left( a\right) \in\mathbb{N}$. Accordingly,
it requires that the capacities $c\left( a\right) $ of arcs also are
integers. Let us state it precisely:
\begin{definition}
Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}. An \textit{integer flow} means a flow
$f:A\rightarrow\mathbb{Q}_{+}$ satisfying $\left( f\left( a\right)
\in\mathbb{N}\text{ for each }a\in A\right) $.
\end{definition}
\begin{theorem}
\label{thm.3b}Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}. Assume that $c\left( a\right) \in\mathbb{N}$
for each $a\in A$. Then,%
\begin{align*}
& \max\left\{ \left\vert f\right\vert \ \mid\ f\text{ is an integer
flow}\right\} \\
& =\min\left\{ c\left( S,\overline{S}\right) \ \mid\ S\subseteq V;\ s\in
S;\ t\notin S\right\} .
\end{align*}
In particular, the left-hand side of this equation is well-defined (i.e.,
there exists a flow $f$ for which $\left\vert f\right\vert $ is maximum).
\end{theorem}
Finally, a third variant (which we shall not prove) makes the same statement
as Theorem \ref{thm.3a} but with $\mathbb{Q}_{+}$ replaced by $\mathbb{R}_{+}$:
\begin{theorem}
\label{thm.3c}Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}, except that $c$ is now a map $A\rightarrow
\mathbb{R}_{+}$ instead of being a map $A\rightarrow\mathbb{Q}_{+}$. (That is,
the capacities of arcs are now allowed to be irrational.) Also, let us
temporarily modify the definition of a flow in such a way that a flow is a map
$A\rightarrow\mathbb{R}_{+}$ instead of being a map $A\rightarrow
\mathbb{Q}_{+}$. Then,%
\[
\max\left\{ \left\vert f\right\vert \ \mid\ f\text{ is a flow}\right\}
=\min\left\{ c\left( S,\overline{S}\right) \ \mid\ S\subseteq V;\ s\in
S;\ t\notin S\right\} .
\]
In particular, the left-hand side of this equation is well-defined (i.e.,
there exists a flow $f$ for which $\left\vert f\right\vert $ is maximum).
\end{theorem}
There are various proofs of these three theorems. In particular, Theorem
\ref{thm.3a} and Theorem \ref{thm.3c} can be viewed as an application of
\textit{linear programming duality}, a fundamental principle in linear
optimization. We will instead proceed elementarily. Along the way, we will see
how to \textbf{construct} a flow $f$ maximizing $\left\vert f\right\vert $ and
an $s$-$t$-cutting subset $S$ minimizing $c\left( S,\overline{S}\right) $
(two problems that occur in real life).
\subsection{The residual digraph}
First, let us define the so-called \textit{residual digraph} of a
flow:\footnote{This definition is somewhat abstract. See the discussion below
and Example \ref{exa.residual-digraph.ex1} for what is really going on.}
\begin{definition}
\label{def.Df}Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}.
\textbf{(a)} If $p$ is a pair $\left( u,v\right) \in V\times V$, then we let
$p^{-1}$ denote the pair $\left( v,u\right) \in V\times V$. (This is simply
a suggestive notation; it has nothing to do with reciprocals of numbers.) We
call $p^{-1}$ the \textit{reversal} of the pair $p$. Notice that $\left(
p^{-1}\right) ^{-1}=a$ for each $p\in V\times V$.
\textbf{(b)} Let $\overleftrightarrow{A}$ be the set $\left\{ 0,1\right\}
\times A$.
For each arc $a\in A$, we define $\overrightarrow{a}\in\overleftrightarrow{A}$
to be the pair $\left( 0,a\right) $, and we define $\overleftarrow{a}%
\in\overleftrightarrow{A}$ to be the pair $\left( 1,a\right) $.
We shall use (some of) these pairs $\overrightarrow{a}$ and $\overleftarrow{a}%
$ as arcs in a multidigraph we shall soon define. Notice that any element of
$\overleftrightarrow{A}$ either has the form $\overrightarrow{a}$ for some
uniquely determined $a\in A$, or has the form $\overleftarrow{a}$ for some
uniquely determined $a\in A$, but not both at the same time.
\textbf{(c)} Let $f:A\rightarrow\mathbb{Q}_{+}$ be any flow on $N$. Define a
subset $A_{f}$ of $\overleftrightarrow{A}$ by%
\[
A_{f}=\left\{ \overrightarrow{a}\ \mid\ a\in A\text{ and }f\left( a\right)
0\right\} .
\]
Define a map $\phi_{f}:A_{f}\rightarrow V\times V$ by%
\begin{align*}
& \left( \phi_{f}\left( \overrightarrow{a}\right) =\phi\left( a\right)
\text{ for each }a\in A\text{ satisfying }f\left( a\right) 0\right) .
\end{align*}
\textbf{(d)} We define the \textit{residual digraph }$D_{f}$ to be the
multidigraph $\left( V,A_{f},\phi_{f}\right) $.
\end{definition}
Let us unpack this definition. The residual digraph $D_{f}$ of a flow $f$ has
the same vertices as the multidigraph $\left( V,A,\phi\right) $ that
underlies the network $N$; but its arcs are different. Namely, the arcs of
$D_{f}$ are described as follows:
\begin{itemize}
\item for any arc $a\in A$ satisfying $f\left( a\right) 0$ (that is, for
any arc $a\in A$ that sees some positive throughput\ by the flow $f$), the
digraph $D_{f}$ has an arc $\overleftarrow{a}$ whose source and target are the
target and source of $a$.
\end{itemize}
Thus, informally speaking, the residual digraph $D_{f}$ shows the
\textquotedblleft wiggle-room\textquotedblright\ for modifying $f$ without
breaking the capacity constraints (ignoring, for the time being, the
conservation constraints). Indeed:
\begin{itemize}
\item an arc $a\in A$ can afford an increase in the flow going through it
(without violating the capacity constraints) if and only if the corresponding
$\overrightarrow{a}$ is an arc of $D_{f}$;
\item an arc $a\in A$ can afford a reduction in the flow going through it
(without violating the capacity constraints) if and only if the corresponding
$\overleftarrow{a}$ is an arc of $D_{f}$.
\end{itemize}
Of course, if we modify the flow on a single arc, then we will most likely
break the conservation constraints. The key to finding a maximum flow is thus
to change a flow in such a way that both capacity and conservation constraints
are preserved; the residual digraph $D_{f}$ is merely the first step.
Notice that the arcs of $D_{f}$ are not arcs of $\left( V,A,\phi\right) $.
\begin{example}
\label{exa.residual-digraph.ex1}Let $f$ be the following flow:%
\[%
%TCIMACRO{\TeXButton{network with flow}{\xymatrix@C=7pc@R=5pc{
%s = 1 \ar[r]^{\alpha: 1 \of2} \ar[dr]_{\gamma: 1 \of3} & 2 \ar[r]^{\beta
%: 0 \of1} \ar[dr]^{\varepsilon: 1 \of1}
%& 4 \ar[dr]^{\mu: 0 \of1} \\
%& 3 \ar[r]_{\delta: 1 \of2} & 5 \ar[r]_{\lambda: 2 \of2} & 6 = t
%}}}%
%BeginExpansion
\xymatrix@C=7pc@R=5pc{
s = 1 \ar[r]^{\alpha: 1 \of2} \ar[dr]_{\gamma: 1 \of3} & 2 \ar[r]^{\beta
: 0 \of1} \ar[dr]^{\varepsilon: 1 \of1}
& 4 \ar[dr]^{\mu: 0 \of1} \\
& 3 \ar[r]_{\delta: 1 \of2} & 5 \ar[r]_{\lambda: 2 \of2} & 6 = t
}%
%EndExpansion
\]
(where, as before, we write \textquotedblleft$f\left( a\right) $ of
$c\left( a\right) $\textquotedblright\ atop each arc $a$). Then, the
residual digraph $D_{f}$ is%
\[%
%TCIMACRO{\TeXButton{residual digraph}{\xymatrix@C=7pc@R=5pc{
%s = 1 \ar@/^1pc/[r]^{\overrightarrow{\alpha}} \ar@/_5pc/[dr]_{\overrightarrow
%{\gamma}} & 2 \ar@/^1pc/[r]^{\overrightarrow{\beta}} \ar@
%/^1pc/[l]^{\overleftarrow{\alpha}} & 4 \ar[dr]^{\overrightarrow{\mu}} \\
%& 3 \ar@/^2pc/[lu]^{\overleftarrow{\gamma}} \ar@/^1pc/[r]^{\overrightarrow
%{\delta}} & 5 \ar@/^1pc/[l]^{\overleftarrow{\delta}} \ar@
%/_1pc/[lu]_{\overleftarrow{\varepsilon}} & 6 = t \ar[l]^{\overleftarrow
%{\lambda}}
%}}}%
%BeginExpansion
\xymatrix@C=7pc@R=5pc{
s = 1 \ar@/^1pc/[r]^{\overrightarrow{\alpha}} \ar@/_5pc/[dr]_{\overrightarrow
{\gamma}} & 2 \ar@/^1pc/[r]^{\overrightarrow{\beta}} \ar@
/^1pc/[l]^{\overleftarrow{\alpha}} & 4 \ar[dr]^{\overrightarrow{\mu}} \\
& 3 \ar@/^2pc/[lu]^{\overleftarrow{\gamma}} \ar@/^1pc/[r]^{\overrightarrow
{\delta}} & 5 \ar@/^1pc/[l]^{\overleftarrow{\delta}} \ar@
/_1pc/[lu]_{\overleftarrow{\varepsilon}} & 6 = t \ar[l]^{\overleftarrow
{\lambda}}
}%
%EndExpansion
.
\]
Notice that the multidigraph $D_{f}$ has cycles even though $\left(
V,A,\phi\right) $ has none!
\end{example}
\subsection{The augmenting path lemma}
The main workhorse of our proof will be the following lemma:
\begin{lemma}
\label{lem.4}Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}.
Let $f:A\rightarrow\mathbb{Q}_{+}$ be a flow.
\textbf{(a)} If the multidigraph $D_{f}$ has a path from $s$ to $t$, then
there is a flow $f^{\prime}$ with a larger value than $f$.
\textbf{(b)} If the multidigraph $D_{f}$ has no path from $s$ to $t$, then
there exists a subset $S$ of $V$ satisfying $s\in V$ and $t\notin V$ and
$c\left( S,\overline{S}\right) =\left\vert f\right\vert $.
\end{lemma}
Before we prove this, we need to lay some more groundwork.
\begin{definition}
Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}.
\textbf{(a)} We identify the maps $g:A\rightarrow\mathbb{Q}$ satisfying
$\left( g\left( a\right) \geq0\text{ for all }a\in A\right) $ (that is,
the maps $g:A\rightarrow\mathbb{Q}$ satisfying $g\left( A\right)
\subseteq\mathbb{Q}_{+}$) with the maps $A\rightarrow\mathbb{Q}_{+}$.
\textbf{(b)} We extend the notations $f^{-}\left( v\right) $ and
$f^{+}\left( v\right) $ from Definition \ref{def.f-f+} to arbitrary maps
$f:A\rightarrow\mathbb{Q}$ (not just maps $f:A\rightarrow\mathbb{Q}_{+}$). Of
course, $f^{-}\left( v\right) $ and $f^{+}\left( v\right) $ will then be
elements of $\mathbb{Q}$, not necessarily of $\mathbb{Q}_{+}$.
We also extend the notation $\left\vert f\right\vert $ from Definition
\ref{def.flow.value} to arbitrary maps $f:A\rightarrow\mathbb{Q}$ (not just
flows). Thus, $\left\vert f\right\vert =f^{+}\left( s\right) -f^{-}\left(
s\right) $ for any map $f:A\rightarrow\mathbb{Q}$.
\textbf{(c)} If $f:A\rightarrow\mathbb{Q}$ and $g:A\rightarrow\mathbb{Q}$ are
two maps, then $f+g$ denotes a new map $A\rightarrow\mathbb{Q}$ that is
defined by%
\[
\left( f+g\right) \left( a\right) =f\left( a\right) +g\left( a\right)
\ \ \ \ \ \ \ \ \ \ \text{for all }a\in A.
\]
\textbf{(d)} We say that a map $f:A\rightarrow\mathbb{Q}$ \textit{satisfies
the conservation constraints} if and only if each $v\in V\setminus\left\{
s,t\right\} $ satisfies $f^{-}\left( v\right) =f^{+}\left( v\right) $.
\end{definition}
Notice that any flow $f:A\rightarrow\mathbb{Q}_{+}$ satisfies the conservation constraints.
\begin{lemma}
\label{lem.5}Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}.
\textbf{(a)} Any two maps $f:A\rightarrow\mathbb{Q}$ and $g:A\rightarrow
\mathbb{Q}$ satisfy $\left\vert f+g\right\vert =\left\vert f\right\vert
+\left\vert g\right\vert $.
\textbf{(b)} Let $f:A\rightarrow\mathbb{Q}$ and $g:A\rightarrow\mathbb{Q}$ be
two maps satisfying the conservation constraints. Then, the map
$f+g:A\rightarrow\mathbb{Q}$ also satisfies the conservation constraints.
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.5} (sketched).]\textbf{(b)} This is exactly as
straightforward as you would expect: Fix $v\in V\setminus\left\{ s,t\right\}
$. Then, the definition of $\left( f+g\right) ^{-}\left( v\right) $ yields%
\begin{align*}
\left( f+g\right) ^{-}\left( v\right) & =\sum_{\substack{a\in A\text{ is
an arc}\\\text{with target }v}}\underbrace{\left( f+g\right) \left(
a\right) }_{\substack{=f\left( a\right) +g\left( a\right) \\\text{(by the
definition of }f+g\text{)}}}=\sum_{\substack{a\in A\text{ is an arc}%
\\\text{with target }v}}\left( f\left( a\right) +g\left( a\right) \right)
\\
& =\underbrace{\sum_{\substack{a\in A\text{ is an arc}\\\text{with target }%
v}}f\left( a\right) }_{\substack{=f^{-}\left( v\right) \\\text{(by the
definition of }f^{-}\left( v\right) \text{)}}}+\underbrace{\sum
_{\substack{a\in A\text{ is an arc}\\\text{with target }v}}g\left( a\right)
}_{\substack{=g^{-}\left( v\right) \\\text{(by the definition of }%
g^{-}\left( v\right) \text{)}}}\\
& =f^{-}\left( v\right) +g^{-}\left( v\right) .
\end{align*}
Similarly, $\left( f+g\right) ^{+}\left( v\right) =f^{+}\left( v\right)
+g^{+}\left( v\right) $. But the map $f$ satisfies the conservation
constraints; hence, $f^{-}\left( v\right) =f^{+}\left( v\right) $.
Similarly, $g^{-}\left( v\right) =g^{+}\left( v\right) $.
Now, $\left( f+g\right) ^{-}\left( v\right) =\underbrace{f^{-}\left(
v\right) }_{=f^{+}\left( v\right) }+\underbrace{g^{-}\left( v\right)
}_{=g^{+}\left( v\right) }=f^{+}\left( v\right) +g^{+}\left( v\right)
=\left( f+g\right) ^{+}\left( v\right) $.
Now forget that we fixed $v$. We thus have proven that each $v\in
V\setminus\left\{ s,t\right\} $ satisfies $\left( f+g\right) ^{-}\left(
v\right) =\left( f+g\right) ^{+}\left( v\right) $. In other words, the
map $f+g$ satisfies the conservation constraints. This proves Lemma
\ref{lem.5} \textbf{(b)}.
\textbf{(a)} The proof (which uses the same ideas as the proof of Lemma
\ref{lem.5} \textbf{(b)}) is left to the reader.
\end{proof}
\begin{lemma}
\label{lem.6}Let $N$, $V$, $A$, $\phi$, $s$, $t$ and $c$ be as in Definition
\ref{def.network.notations}. Let $f:A\rightarrow\mathbb{Q}_{+}$ be a flow.
Let $\mathbf{p}$ be a path from $s$ to $t$ in the multidigraph $D_{f}=\left(
V,A_{f},\phi_{f}\right) $.
Let $P$ be the set of arcs of $\mathbf{p}$. Thus, $P\subseteq A_{f}%
\subseteq\overleftrightarrow{A}$.
Let $\rho\in\mathbb{Q}$.
Define a map $g:A\rightarrow\mathbb{Q}$ by setting%
\[
g\left( a\right) =%
\begin{cases}
\rho, & \text{if }\overrightarrow{a}\in P;\\
-\rho, & \text{if }\overleftarrow{a}\in P;\\
0, & \text{otherwise}%
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }a\in A.
\]
(This is well-defined, because the conditions $\overrightarrow{a}\in P$ and
$\overleftarrow{a}\in P$ cannot hold at the same time\footnotemark.)
\textbf{(a)} This map $g$ satisfies the conservation constraints (i.e., each
$v\in V\setminus\left\{ s,t\right\} $ satisfies $g^{-}\left( v\right)
=g^{+}\left( v\right) $).
\textbf{(b)} We have $\left\vert g\right\vert =\rho$.
\end{lemma}
\footnotetext{\textit{Proof.} Let $a\in A$. We must show that the conditions
$\overrightarrow{a}\in P$ and $\overleftarrow{a}\in P$ cannot hold at the same
time.
\par
Assume the contrary. Thus, $\overrightarrow{a}\in P$ and $\overleftarrow{a}\in
P$ both hold. The definition of $\phi_{f}$ shows that $\phi_{f}\left(
\overrightarrow{a}\right) =\phi\left( a\right) $; thus, the target of
$\overrightarrow{a}$ is the target of $a$. But the definition of $\phi_{f}$
also shows that $\phi_{f}\left( \overleftarrow{a}\right) =\left(
\phi\left( a\right) \right) ^{-1}$; thus, the source of $\overleftarrow{a}$
is the target of $a$. Hence, the source of $\overleftarrow{a}$ and the target
of $\overrightarrow{a}$ are identical (since they both are the target of $a$).
\par
But both $\overleftarrow{a}$ and $\overrightarrow{a}$ are arcs of the path
$\mathbf{p}$ (since $\overrightarrow{a}\in P$ and $\overleftarrow{a}\in P$).
Since the vertices of a path are distinct, this shows that the source of
$\overleftarrow{a}$ and the target of $\overrightarrow{a}$ are distinct unless
$\overleftarrow{a}$ directly follows $\overrightarrow{a}$ on the path
$\mathbf{p}$. Therefore, $\overleftarrow{a}$ directly follows
$\overrightarrow{a}$ on the path $\mathbf{p}$ (since the source of
$\overleftarrow{a}$ and the target of $\overrightarrow{a}$ are equal). But an
analogous argument shows that $\overrightarrow{a}$ directly follows
$\overleftarrow{a}$ on the path $\mathbf{p}$. The preceding two sentences
contradict each other. This contradiction shows that our assumption was false.
Qed.}
\begin{proof}
[Proof of Lemma \ref{lem.6} (sketched).]\textbf{(a)} Let $v\in V\setminus
\left\{ s,t\right\} $ be arbitrary. We must prove that $g^{-}\left(
v\right) =g^{+}\left( v\right) $.
If $v$ is not a vertex of the path $\mathbf{p}$, then this is obvious (since
in this case, each arc $a$ having source $v$ or target $v$ satisfies $g\left(
a\right) =0$ (since neither $\overrightarrow{a}\in P$ nor $\overleftarrow{a}%
\in P$), and thus we have $g^{-}\left( v\right) =0$ and $g^{+}\left(
v\right) =0$).
Thus, we WLOG assume that $v$ is a vertex of the path $\mathbf{p}$. Since $v$
is neither the starting point nor the ending point of this path $\mathbf{p}$
(because $v\in V\setminus\left\{ s,t\right\} $, but the starting and ending
points of $\mathbf{p}$ are $s$ and $t$), we thus conclude that there is
exactly one arc $x\in P$ having source $v$, and exactly one arc $y\in P$
having target $v$ (because $\mathbf{p}$ is a path, and $P$ is the set of its
arcs). Consider these arcs $x$ and $y$. Notice that $x$ and $y$ are arcs of
the multidigraph $D_{f}$, not arcs of $\left( V,A,\phi\right) $.
The arcs $x$ and $y$ are distinct\footnote{\textit{Proof.} Assume the
contrary. Thus, $x=y$. Hence, the arc $x=y$ has source $v$ (since $x$ has
source $v$) and target $v$ (since $y$ has target $v$). Thus, the source and
the target of this arc $x$ are equal (because they are both equal to $v$).
\par
But the arc $x$ is an arc of the path $\mathbf{p}$ (since $x\in P$), and thus
its source and its target are two different vertices of $\mathbf{p}$.
Therefore, its source and its target are distinct (since the vertices of
$\mathbf{p}$ are distinct). This contradicts the fact that its source and its
target are equal. This is a contradiction, qed.}.
We have%
\begin{align*}
y & \in P\subseteq A_{f}=\left\{ \overrightarrow{a}\ \mid\ a\in A\text{ and
}f\left( a\right) 0\right\} \\
& =\left\{ \overrightarrow{b}\ \mid\ b\in A\text{ and }f\left( b\right)
0\right\}
\end{align*}
(here, we renamed the indices $a$ as $b$). Thus, either $y\in\left\{
\overrightarrow{b}\ \mid\ b\in A\text{ and }f\left( b\right) 0\right\} $.
We have
\[
x\in P\subseteq A_{f}=\left\{ \overrightarrow{a}\ \mid\ a\in A\text{ and
}f\left( a\right) 0\right\} .
\]
Thus, either $x\in\left\{ \overrightarrow{a}\ \mid\ a\in A\text{ and
}f\left( a\right) 0\right\} $.
Hence, we are in one of the following two cases:
\begin{statement}
\textit{Case 1:} We have $x\in\left\{ \overrightarrow{a}\ \mid\ a\in A\text{
and }f\left( a\right) 0\right\} $.
\end{statement}
Let us consider Case 2. In this case, we have $x\in\left\{ \overleftarrow{a}%
\ \mid\ a\in A\text{ and }f\left( a\right) >0\right\} $. In other words,
$x=\overleftarrow{a}$ for some $a\in A$ satisfying $f\left( a\right) >0$.
Consider this $a$. Since $\overleftarrow{a}=x\in P$, we have $g\left(
a\right) =-\rho$ (by the definition of $g$).
But recall that either $y\in\left\{ \overrightarrow{b}\ \mid\ b\in A\text{
and }f\left( b\right) 0\right\} $. Hence, we are in one of the following two subcases:
\begin{statement}
\textit{Subcase 2.1:} We have $y\in\left\{ \overrightarrow{b}\ \mid\ b\in
A\text{ and }f\left( b\right) 0\right\} $.
\end{statement}
Let us consider Subcase 2.2. In this subcase, we have $y\in\left\{
\overleftarrow{b}\ \mid\ b\in A\text{ and }f\left( b\right) >0\right\} $.
In other words, $y=\overleftarrow{b}$ for some $b\in A$ satisfying $f\left(
b\right) >0$. Consider this $b$. Since $\overleftarrow{b}=y\in P$, we have
$g\left( b\right) =-\rho$.
Here is how the two arcs $x$ and $y$ look like in the multidigraph $D_{f}$:%
\[%
%TCIMACRO{\TeXButton{two arcs}{\xymatrix{
%& \ar[r]^y & v \ar[r]^x &
%}}}%
%BeginExpansion
\xymatrix{
& \ar[r]^y & v \ar[r]^x &
}%
%EndExpansion
.
\]
And here is how the corresponding arcs $a$ and $b$ look like in the underlying
multidigraph $\left( V,A,\phi\right) $ of our network:%
\begin{equation}%
%TCIMACRO{\TeXButton{two arcs}{\xymatrix{
%& & v \ar[l]_{b} & \ar[l]_{a}
%}} }%
%BeginExpansion
\xymatrix{
& & v \ar[l]_{b} & \ar[l]_{a}
}
%EndExpansion
\label{pf.lem.6.a.sc2.2.3}%
\end{equation}
(because $\overleftarrow{a}=x$ and $\overleftarrow{b}=y$). Both arcs $a$ and
$b$ are sent to $-\rho$ by $g$ (since $g\left( a\right) =-\rho$ and
$g\left( b\right) =-\rho$). All other arcs in $A$ having source or target
$v$ are sent to $0$ by $g$\ \ \ \ \footnote{\textit{Proof.} Let $d$ be any arc
in $A$ having source or target $v$. Assume that $d$ is distinct from both $a$
and $b$. We must prove that $g\left( d\right) =0$.
\par
From $d\neq a$, we obtain $\overleftarrow{d}\neq\overleftarrow{a}=x$. Also,
clearly, $\overrightarrow{d}\neq\overleftarrow{a}=x$. From $d\neq b$, we
obtain $\overleftarrow{d}\neq\overleftarrow{b}=y$. Also, clearly,
$\overrightarrow{d}\neq\overleftarrow{b}=y$.
\par
Let us first assume that $d$ has source $v$. Thus, the arc $\overleftarrow{d}$
of $D_{f}$ has target $v$ (by the definition of $D_{f}$). But the only arc in
$P$ having target $v$ is $y$ (by the definition of $y$). Thus, if we had
$\overleftarrow{d}\in P$, then we would have $\overleftarrow{d}=y$ (since
$\overleftarrow{d}$ would be an arc in $P$ having target $v$), which would
contradict $\overleftarrow{d}\neq y$. Hence, we cannot have $\overleftarrow{d}%
\in P$.
\par
Recall again that $d$ has source $v$. Thus, the arc $\overrightarrow{d}$ of
$D_{f}$ has source $v$ (by the definition of $D_{f}$). But the only arc in $P$
having source $v$ is $x$ (by the definition of $x$). Thus, if we had
$\overrightarrow{d}\in P$, then we would have $\overrightarrow{d}=x$ (since
$\overrightarrow{d}$ would be an arc in $P$ having source $v$), which would
contradict $\overrightarrow{d}\neq x$. Hence, we cannot have
$\overrightarrow{d}\in P$.
\par
Hence, we have neither $\overleftarrow{d}\in P$ nor $\overrightarrow{d}\in P$.
According to the definition of $g$, we thus conclude that $g\left( d\right)
=0$.
\par
Now, forget our assumption that $d$ has source $v$. We thus have shown that if
$d$ has source $v$, then $g\left( d\right) =0$. A similar argument shows
that if $d$ has target $v$, then $g\left( d\right) =0$. Combining these two
statements, we conclude that we always have $g\left( d\right) =0$ (because
$d$ has source or target $v$). This completes our proof of $g\left( d\right)
=0$.}. Hence, in particular, all arcs in $A$ having target $v$ are sent to $0$
by $g$, except for the arc $a$. Thus, $g^{-}\left( v\right) =g\left(
a\right) =-\rho$. A similar argument shows that $g^{+}\left( v\right)
=-\rho$. Thus, $g^{-}\left( v\right) =-\rho=g^{+}\left( v\right) $. Thus,
$g^{-}\left( v\right) =g^{+}\left( v\right) $ is proven in Subcase 2.2.
The proof in Subcase 2.1 is rather similar, with the little difference that
now the picture (\ref{pf.lem.6.a.sc2.2.3}) is replaced by%
\[%
%TCIMACRO{\TeXButton{two arcs}{\xymatrix{
%& \ar[r]^y & v & \ar[l]_{x}
%}}}%
%BeginExpansion
\xymatrix{
& \ar[r]^y & v & \ar[l]_{x}
}%
%EndExpansion
,
\]
and so we have $g^{-}\left( v\right) =\left( -\rho\right) +\rho=0$ and
$g^{+}\left( v\right) =0$. But again the result is the same.
Thus, Case 2 is settled. The proof in Case 1 is similar (again, we need to
consider two subcases, depending on whether $y\in\left\{ \overrightarrow{b}%
\ \mid\ b\in A\text{ and }f\left( b\right) 0\right\} $).
Altogether, we have now proven $g^{-}\left( v\right) =g^{+}\left( v\right)
$ in each possible case.
Now, forget that we fixed $v$. We thus have shown that each $v\in
V\setminus\left\{ s,t\right\} $ satisfies $g^{-}\left( v\right)
=g^{+}\left( v\right) $. In other words, $g$ satisfies the conservation
constraints. This proves Lemma \ref{lem.6} \textbf{(a)}.
\textbf{(b)} This is somewhat similar to our above proof of Lemma \ref{lem.6}
\textbf{(a)}, with the vertex $s$ playing the role of $v$.
The vertex $s$ is the starting point of the path $\mathbf{p}$, but not its
ending point (since its ending point is $t\neq s$). Hence, there is exactly
one arc $x\in P$ having source $s$, and there are no arcs $y\in P$ having
target $s$.
We have
\[
x\in P\subseteq A_{f}=\left\{ \overrightarrow{a}\ \mid\ a\in A\text{ and
}f\left( a\right) 0\right\} .
\]
Thus, either $x\in\left\{ \overrightarrow{a}\ \mid\ a\in A\text{ and
}f\left( a\right) 0\right\} $.
Hence, we are in one of the following two cases:
\begin{statement}
\textit{Case 1:} We have $x\in\left\{ \overrightarrow{a}\ \mid\ a\in A\text{
and }f\left( a\right) 0\right\} $.
\end{statement}
Let us consider Case 2. In this case, we have $x\in\left\{ \overleftarrow{a}%
\ \mid\ a\in A\text{ and }f\left( a\right) >0\right\} $. In other words,
$x=\overleftarrow{a}$ for some $a\in A$ satisfying $f\left( a\right) >0$.
Consider this $a$. Since $\overleftarrow{a}=x\in P$, we have $g\left(
a\right) =-\rho$ (by the definition of $g$).
Thus, the arc $a$ is sent to $-\rho$ by $g$. All other arcs in $A$ having
source or target $s$ are sent to $0$ by $g$\ \ \ \ \footnote{This is easy to
check -- just as in the above proof of Lemma \ref{lem.6} \textbf{(a)}.}.
Hence, in particular, all arcs in $A$ having target $s$ are sent to $0$ by
$g$, except for the arc $a$. Thus, $g^{-}\left( s\right) =g\left( a\right)
=-\rho$. A similar argument shows that $g^{+}\left( s\right) =0$. Now, the
definition of $\left\vert g\right\vert $ yields $\left\vert g\right\vert
=\underbrace{g^{+}\left( s\right) }_{=0}-\underbrace{g^{-}\left( s\right)
}_{=-\rho}=0-\left( -\rho\right) =\rho$. Thus, Lemma \ref{lem.6}
\textbf{(b)} is proven in Case 2.
A similar argument works in Case 1. Thus, Lemma \ref{lem.6} \textbf{(b)} is
always proven.
\end{proof}
We are now ready to prove Lemma \ref{lem.4}:
\begin{proof}
[Proof of Lemma \ref{lem.4} (sketched).]\textbf{(a)} Assume that the
multidigraph $D_{f}$ has a path from $s$ to $t$. Fix such a path, and denote
it by $\mathbf{p}$.
Let $P$ be the set of arcs of $\mathbf{p}$. Thus, $P\subseteq A_{f}$ (since
$\mathbf{p}$ is a path in $D_{f}=\left( V,A_{f},\phi_{f}\right) $). The path
$\mathbf{p}$ is a path from $s$ to $t$, and thus has at least one arc (since
$s\neq t$); hence, the set $P$ is nonempty.
For each arc $b\in P$, we define a number $\rho_{b}\in\mathbb{Q}$ by%
\[
\rho_{b}=%
\begin{cases}
c\left( a\right) -f\left( a\right) , & \text{if }b=\overrightarrow{a}%
\text{ for some }a\in A;\\
f\left( a\right) , & \text{if }b=\overleftarrow{a}\text{ for some }a\in A
\end{cases}
.
\]
(This is well-defined, because each $b\in P$ either has the form
$b=\overrightarrow{a}$ for some $a\in A$ or has the form $b=\overleftarrow{a}$
for some $a\in A$; this follows from $b\in P\subseteq A_{f}$.)
For each arc $b\in P$, the number $\rho_{b}$ is
positive\footnote{\textit{Proof.} Let $b\in P$ be any arc. We must prove that
$\rho_{b}$ is positive.
\par
We have $b\in P\subseteq A_{f}=\left\{ \overrightarrow{a}\ \mid\ a\in A\text{
and }f\left( a\right) 0\right\} $.
Thus, either $b\in\left\{ \overrightarrow{a}\ \mid\ a\in A\text{ and
}f\left( a\right) 0\right\} $.
So we are in one of the following two cases:
\par
\textit{Case 1:} We have $b\in\left\{ \overrightarrow{a}\ \mid\ a\in A\text{
and }f\left( a\right) 0\right\} $.
\par
Let us first consider Case 1. In this case, we have $b\in\left\{
\overrightarrow{a}\ \mid\ a\in A\text{ and }f\left( a\right) 0$ (since $f\left( a\right) 0\right\} $.
Thus, $b=\overleftarrow{a}$ for some $a\in A$ satisfying $f\left( a\right)
>0$. Consider this $a$. The definition of $\rho_{b}$ yields $\rho_{b}=f\left(
a\right) $ (since $b=\overleftarrow{a}$), and thus $\rho_{b}=f\left(
a\right) >0$. Thus, we have shown that $\rho_{b}$ is positive in Case 2.
\par
We have now proven that $\rho_{b}$ is positive in both Cases 1 and 2. Hence,
$\rho_{b}$ is always positive, qed.}. We now define $\rho\in\mathbb{Q}$ by
$\rho=\min\left\{ \rho_{b}\mid b\in P\right\} $. (This is well-defined,
since $P$ is nonempty and finite.) Then, $\rho$ is positive (since all
$\rho_{b}$ are positive), so that $\rho\geq0$.
Now, define a map $g:A\rightarrow\mathbb{Q}$ as in Lemma \ref{lem.6}. Then,
Lemma \ref{lem.6} \textbf{(a)} shows that the map $g$ satisfies the
conservation constraints. Also, the map $f$ satisfies the conservation
constraints (since $f$ is a flow). Hence, Lemma \ref{lem.5} \textbf{(b)} shows
that the map $f+g$ satisfies the conservation constraints. Also, Lemma
\ref{lem.5} \textbf{(a)} shows that $\left\vert f+g\right\vert =\left\vert
f\right\vert +\underbrace{\left\vert g\right\vert }_{\substack{=\rho
\\\text{(by Lemma \ref{lem.6} \textbf{(b)})}}}=\left\vert f\right\vert +\rho$.
Next, we claim that the map $f+g$ also satisfies the capacity constraints --
i.e., that we have%
\begin{equation}
0\leq\left( f+g\right) \left( a\right) \leq c\left( a\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }a\in A. \label{pf.lem.4.a.capac1}%
\end{equation}
[\textit{Proof of (\ref{pf.lem.4.a.capac1}):} Fix $a\in A$. Recall that $f$ is
a flow; thus, $f$ satisfies the capacity constraints. Hence, $0\leq f\left(
a\right) \leq c\left( a\right) $.
Now, we are in one of the following three cases:
\begin{statement}
\textit{Case 1:} We have $\overrightarrow{a}\in P$.
\end{statement}
\begin{statement}
\textit{Case 2:} We have $\overleftarrow{a}\in P$.
\end{statement}
\begin{statement}
\textit{Case 3:} We have neither $\overrightarrow{a}\in P$ nor
$\overleftarrow{a}\in P$.
\end{statement}
Let us first consider Case 3. In this case, the definition of $g$ yields
$g\left( a\right) =0$. Thus, $\left( f+g\right) \left( a\right)
=f\left( a\right) +\underbrace{g\left( a\right) }_{=0}=f\left( a\right)
$. Hence, $0\leq f\left( a\right) \leq c\left( a\right) $ rewrites as
$0\leq\left( f+g\right) \left( a\right) \leq c\left( a\right) $. Thus,
(\ref{pf.lem.4.a.capac1}) is proven in Case 3.
Let us now consider Case 2. In this case, we have $\overleftarrow{a}\in P$.
Hence, the definition of $g$ yields $g\left( a\right) =-\rho$. But the
definition of $\rho$ yields $\rho=\min\left\{ \rho_{b}\mid b\in P\right\}
\leq\rho_{\overleftarrow{a}}$ (since $\overleftarrow{a}\in P$ and thus
$\rho_{\overleftarrow{a}}\in\left\{ \rho_{b}\mid b\in P\right\} $). Also,
the definition of $\rho_{\overleftarrow{a}}$ yields $\rho_{\overleftarrow{a}%
}=f\left( a\right) $. Hence, $\rho\leq\rho_{\overleftarrow{a}}=f\left(
a\right) $. Now, $\left( f+g\right) \left( a\right) =f\left( a\right)
+\underbrace{g\left( a\right) }_{=-\rho}=f\left( a\right) -\rho\geq0$
(since $\rho\leq f\left( a\right) $). Combining this with $\left(
f+g\right) \left( a\right) =f\left( a\right) +\underbrace{g\left(
a\right) }_{=-\rho}=f\left( a\right) -\underbrace{\rho}_{\geq0}\leq
f\left( a\right) \leq c\left( a\right) $, we obtain $0\leq\left(
f+g\right) \left( a\right) \leq c\left( a\right) $. Thus,
(\ref{pf.lem.4.a.capac1}) is proven in Case 2.
Let us finally consider Case 1. In this case, we have $\overrightarrow{a}\in
P$. Hence, the definition of $g$ yields $g\left( a\right) =\rho$. But the
definition of $\rho$ yields $\rho=\min\left\{ \rho_{b}\mid b\in P\right\}
\leq\rho_{\overrightarrow{a}}$ (since $\overrightarrow{a}\in P$ and thus
$\rho_{\overrightarrow{a}}\in\left\{ \rho_{b}\mid b\in P\right\} $). Also,
the definition of $\rho_{\overrightarrow{a}}$ yields $\rho_{\overrightarrow{a}%
}=c\left( a\right) -f\left( a\right) $. Hence, $\rho\leq\rho
_{\overrightarrow{a}}=c\left( a\right) -f\left( a\right) $. Now, $\left(
f+g\right) \left( a\right) =f\left( a\right) +\underbrace{g\left(
a\right) }_{=\rho}=f\left( a\right) +\rho\leq c\left( a\right) $ (since
$\rho\leq c\left( a\right) -f\left( a\right) $). Combining this with
$\left( f+g\right) \left( a\right) =f\left( a\right)
+\underbrace{g\left( a\right) }_{=\rho}=f\left( a\right) +\underbrace{\rho
}_{\geq0}\geq f\left( a\right) \geq0$, we obtain $0\leq\left( f+g\right)
\left( a\right) \leq c\left( a\right) $. Thus, (\ref{pf.lem.4.a.capac1})
is proven in Case 1.
We have thus proven (\ref{pf.lem.4.a.capac1}) in all three Cases 1, 2 and 3.
Thus, (\ref{pf.lem.4.a.capac1}) is proven.]
From (\ref{pf.lem.4.a.capac1}), we conclude in particular that $\left(
f+g\right) \left( a\right) \geq0$ for each $a\in A$. Thus, $f+g$ is a map
$A\rightarrow\mathbb{Q}_{+}$. We have shown that this map $f+g:A\rightarrow
\mathbb{Q}_{+}$ satisfies both the capacity constraints and the conservation
constraints. In other words, $f+g$ is a flow (by the definition of a flow).
Furthermore, this flow has value $\left\vert f+g\right\vert =\left\vert
f\right\vert +\rho>\left\vert f\right\vert $ (since $\rho$ is positive). In
other words, it has a larger value than $f$. Thus, there is a flow $f^{\prime
}$ with a larger value than $f$ (namely, $f^{\prime}=f+g$). This proves Lemma
\ref{lem.4} \textbf{(a)}.
\textbf{(b)} Assume that the multidigraph $D_{f}$ has no path from $s$ to $t$.
We must prove that there exists a subset $S$ of $V$ satisfying $s\in V$ and
$t\notin V$ and $c\left( S,\overline{S}\right) =\left\vert f\right\vert $.
Indeed, define a subset $S$ of $V$ by%
\[
S=\left\{ v\in V\ \mid\ \text{the multidigraph }D_{f}\text{ has a path from
}s\text{ to }v\right\} .
\]
We shall show that $s\in S$ and $t\notin S$ and $c\left( S,\overline
{S}\right) =\left\vert f\right\vert $. This will clearly complete the proof
of Lemma \ref{lem.4} \textbf{(b)}.
First of all, the multidigraph $D_{f}$ clearly has a path from $s$ to $s$
(namely, the trivial path $\left( s\right) $). In other words, $s\in S$ (by
the definition of $S$).
Furthermore, the multidigraph $D_{f}$ has no path from $s$ to $t$ (by
assumption). In other words, $t\notin S$ (by the definition of $S$).
It thus remains to show that $c\left( S,\overline{S}\right) =f$.
We first notice the following:
\begin{statement}
\textit{Observation 1:} Let $b\in A_{f}$ be an arc whose source belongs to
$S$. Then, the target of $b$ also belongs to $S$.
\end{statement}
[\textit{Proof of Observation 1:} Let $u$ be the source of the arc $b$. Then,
$u\in S$ (since the source of $b$ belongs to $S$). In other words, the
multidigraph $D_{f}$ has a path from $s$ to $u$ (by the definition of $S$).
Fix such a path, and denote it by $\mathbf{p}$.
Also, let $v$ be the target of the arc $b$. The arc $b$ is an arc of the
multidigraph $D_{f}$ (since $b\in A_{f}$), and its source is the ending point
of the path $\mathbf{p}$ (namely, the point $u$). Thus, we can extend the path
$\mathbf{p}$ by the arc $b$ (that is, we append the arc $b$ and the vertex $v$
to the end of the path $\mathbf{p}$) to obtain a walk from $s$ to $v$ in
$D_{f}$. Hence, there exists a walk from $s$ to $v$ in $D_{f}$. Thus,
Proposition \ref{prop.multidigraph.walk-to-path} (applied to $D_{f}$ and $v$
instead of $D$ and $t$) yields that there exists a path from $s$ to $v$ in
$D_{f}$. In other words, the multidigraph $D_{f}$ has a path from $s$ to $v$.
In other words, $v\in S$ (by the definition of $S$). In other words, the
target of $b$ belongs to $S$ (since $v$ is the target of $b$). This proves
Observation 1.]
Next, we observe that%
\begin{equation}
f\left( a\right) =0\ \ \ \ \ \ \ \ \ \ \text{for each }a\in\left[
\overline{S},S\right] . \label{pf.lem.4.b.3}%
\end{equation}
[\textit{Proof of (\ref{pf.lem.4.b.3}):} Let $a\in\left[ \overline
{S},S\right] $. Thus, $a\in A$ is an arc whose source belongs to
$\overline{S}$ and whose target belongs to $S$ (by the definition of $\left[
\overline{S},S\right] $).
We must prove that $f\left( a\right) =0$. Assume the contrary. Thus,
$f\left( a\right) \neq0$, so that $f\left( a\right) >0$ (since $f\left(
a\right) \geq0$). By the definition of $A_{f}$, we thus have
$\overleftarrow{a}\in A_{f}$. But the source of the arc $\overleftarrow{a}$ is
the target of $a$, and therefore belongs to $S$ (since the target of $a$
belongs to $S$). Hence, Observation 1 (applied to $b=\overleftarrow{a}$)
yields that the target of $\overleftarrow{a}$ also belongs to $S$. Since the
target of $\overleftarrow{a}$ is the source of $a$, this means that the source
of $a$ belongs to $S$. This contradicts the fact that the source of $a$
belongs to $\overline{S}$. This contradiction shows that our assumption was
false. Hence, $f\left( a\right) =0$ holds, and (\ref{pf.lem.4.b.3}) is proven.]
Similarly, we have%
\begin{equation}
f\left( a\right) =c\left( a\right) \ \ \ \ \ \ \ \ \ \ \text{for each
}a\in\left[ S,\overline{S}\right] . \label{pf.lem.4.b.4}%
\end{equation}
[\textit{Proof of (\ref{pf.lem.4.b.4}):} Let $a\in\left[ S,\overline
{S}\right] $. Thus, $a\in A$ is an arc whose source belongs to $S$ and whose
target belongs to $\overline{S}$ (by the definition of $\left[ S,\overline
{S}\right] $).
We must prove that $f\left( a\right) =c\left( a\right) $. Assume the
contrary. Thus, $f\left( a\right) \neq c\left( a\right) $, so that
$f\left( a\right) q$ for all $q\in\mathbb{Q}$). In other words, some arcs $a$ may have
\textquotedblleft infinite capacity\textquotedblright, which means that the
capacity constraints for these arcs $a$ simply say that $0\leq f\left(
a\right) $ (without requiring $f\left( a\right) $ to be $\leq$ to anything
specific). Prove the following:
\textbf{(a)} Theorem \ref{thm.3a} and Theorem \ref{thm.3b} still hold in this
generality, if we additionally assume that there exists \textbf{some} subset
$S$ of $V$ satisfying $s\in S$ and $t\notin S$ and $c\left( S,\overline
{S}\right) <\infty$.
\textbf{(b)} If every subset $S$ of $V$ satisfying $s\in S$ and $t\notin S$
satisfies $c\left( S,\overline{S}\right) =\infty$, then prove that, for
every $n\in\mathbb{N}$, there exists an integer flow $f$ of value $\left\vert
f\right\vert =n$.
\end{exercise}
\section{Application: Bipartite matching}
\subsection{Simple graphs and multigraphs}
As we said, the max-flow-min-cut theorems (particularly, Theorem \ref{thm.3b})
have multiple applications. In many of these applications, the network isn't
visible right away, but instead has to be constructed. Let me present one such
application: the bipartite matching problem.
This problem is concerned with undirected graphs, so let us first define the
latter. Again, there are two types of undirected graphs: the simple graphs and
the multigraphs. We will use the latter, but let us define both of them. We
begin by defining simple graphs.
\begin{definition}
If $W$ is a set, then $\mathcal{P}_{2}\left( W\right) $ shall mean the set
of all $2$-element subsets of $W$. For example,%
\[
\mathcal{P}_{2}\left( \left\{ 1,2,3,4\right\} \right) =\left\{ \left\{
1,2\right\} ,\left\{ 1,3\right\} ,\left\{ 1,4\right\} ,\left\{
2,3\right\} ,\left\{ 2,4\right\} ,\left\{ 3,4\right\} \right\} .
\]
\end{definition}
\begin{definition}
A \textit{simple graph} is defined to be a pair $\left( W,E\right) $
consisting of a finite set $W$ and a subset $E$ of $\mathcal{P}_{2}\left(
W\right) $. The elements of $W$ are called the \textit{vertices} of this
simple graph; the elements of $E$ are called its \textit{edges}. If $e$ is an
edge of a simple graph, then the two vertices contained in $e$ are called the
\textit{endpoints} of $e$. Moreover, if $u$ and $v$ are the two endpoints of
an edge $e$, then we say that the edge $e$ \textit{joins} $u$ with $v$.
\end{definition}
\begin{example}
\label{exa.graph.1}\textbf{(a)} The pair%
\[
\left( \left\{ 1,2,3\right\} ,\left\{ \left\{ 1,3\right\} ,\left\{
2,3\right\} \right\} \right)
\]
is a simple graph. Its vertices are $1,2,3$. Its edges are $\left\{
1,3\right\} $ and $\left\{ 2,3\right\} $. The edge $\left\{ 1,3\right\} $
has endpoints $1$ and $3$, and can also be written as $\left\{ 3,1\right\} $.
\textbf{(b)} The pair
\[
\left( \left\{ 1,3,5\right\} ,\varnothing\right)
\]
is a simple graph. Its vertices are $1,3,5$. It has no edges.
\end{example}
Note that a $1$-element set $\left\{ v\right\} $ can never be the edge of a
simple graph, at least according to our definition of a simple graph. Thus,
the two endpoints of an edge must always be distinct. (Some authors use a
slightly different definition of a simple graph, which uses $W\cup
\mathcal{P}_{2}\left( W\right) $ instead of $\mathcal{P}_{2}\left(
W\right) $; with this definition, the two endpoints of an edge could be equal.)
A simple graph $\left( W,E\right) $ can be visually represented as follows:
\begin{itemize}
\item For each vertex $v\in W$, choose a point in the plane and label it with
a \textquotedblleft$v$\textquotedblright.
\item For each edge $\left\{ u,v\right\} \in E$, draw a curve from the point
labelled \textquotedblleft$u$\textquotedblright\ to the point labelled
\textquotedblleft$v$\textquotedblright.
\end{itemize}
There are many ways to represent a given graph.
\begin{example}
\textbf{(a)} The simple graph $\left( \left\{ 1,2,3\right\} ,\left\{
\left\{ 1,3\right\} ,\left\{ 2,3\right\} \right\} \right) $ from Example
\ref{exa.graph.1} \textbf{(a)} can be represented as follows:%
\[%
%TCIMACRO{\TeXButton{graph on 1,2,3}{\xymatrix{
%& 2 \are[dr] \\
%1 \are[rr] & & 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \are[dr] \\
1 \are[rr] & & 3
}%
%EndExpansion
.
\]
It can also be represented as follows:%
\[%
%TCIMACRO{\TeXButton{graph on 1,2,3}{\xymatrix{
%1 \are[rd] & & 2 \are[ld] \\
%& 3
%}}}%
%BeginExpansion
\xymatrix{
1 \are[rd] & & 2 \are[ld] \\
& 3
}%
%EndExpansion
.
\]
\textbf{(b)} The simple graph $\left( \left\{ 1,3,5\right\} ,\varnothing
\right) $ from Example \ref{exa.graph.1} \textbf{(b)} can be represented as
follows:%
\[%
%TCIMACRO{\TeXButton{graph on 1,3,5}{\xymatrix{
%1 & 5 & 3
%}}}%
%BeginExpansion
\xymatrix{
1 & 5 & 3
}%
%EndExpansion
.
\]
\end{example}
Note that an edge of a simple graph is uniquely determined by its two
endpoints: indeed, it is the set consisting of these two endpoints.
Multigraphs are similar to simple graphs, except that this is no longer true:
their edges are not uniquely determined by their endpoints any more, but
rather have \textquotedblleft their own identities\textquotedblright. Here is
how multigraphs are defined:
\begin{definition}
A \textit{multigraph} is a triple $\left( W,E,\psi\right) $, where $W$ and
$E$ are finite sets and where $\psi$ is a map from $E$ to $\mathcal{P}%
_{2}\left( W\right) $. The elements of $W$ are called the \textit{vertices}
of this multigraph; the elements of $E$ are called its \textit{edges}. If $e$
is an edge of a multigraph $\left( W,E,\psi\right) $, then the two elements
of the set $\psi\left( e\right) \in\mathcal{P}_{2}\left( W\right) $ are
called the \textit{endpoints} of this edge $e$. If $\left( W,E,\psi\right) $
is a multigraph, and if $w\in W$ and $e\in E$, then we say that the edge $e$
\textit{contains} the vertex $w$ if and only if $w\in\psi\left( e\right) $
(that is, if and only if $w$ is an endpoint of $e$).
\end{definition}
\begin{example}
\label{exa.multigraph.1}Let $\alpha,\beta,\gamma,\delta$ be any four distinct
objects (it doesn't matter which objects we take; for example, $10,11,12,13$
do the job). Let $W$ be the set $\left\{ 1,2,3\right\} $, and let $E$ be the
set $\left\{ \alpha,\beta,\gamma,\delta\right\} $. Let $\psi:E\rightarrow
\mathcal{P}_{2}\left( W\right) $ be the map given by%
\begin{align*}
\psi\left( \alpha\right) & =\left\{ 1,3\right\}
,\ \ \ \ \ \ \ \ \ \ \psi\left( \beta\right) =\left\{ 2,3\right\} ,\\
\psi\left( \gamma\right) & =\left\{ 1,3\right\}
,\ \ \ \ \ \ \ \ \ \ \psi\left( \delta\right) =\left\{ 2,1\right\} .
\end{align*}
Then, the triple $\left( W,E,\psi\right) $ is a multigraph. Its vertices are
$1,2,3$; its edges are $\alpha,\beta,\gamma,\delta$. The edge $\alpha$ has
endpoints $1$ and $3$; so does the edge $\gamma$.
\end{example}
A multigraph $\left( W,E,\psi\right) $ is visually represented in the same
way as a simple graph $\left( W,E\right) $, with one difference: An edge
$e\in E$ is now drawn as a curve from the point labelled by its one endpoint
to the point labelled by its other endpoint, and we furthermore label this
curve with an \textquotedblleft$e$\textquotedblright.
\begin{example}
The multigraph $\left( W,E,\psi\right) $ from Example \ref{exa.multigraph.1}
can be represented as follows:%
\[%
%TCIMACRO{\TeXButton{multigraph}{\xymatrix{
%& 2 \are[dl]_{\delta} \are[dd]^{\beta} \\
%1 \are[rd]_{\gamma} \are@/_3pc/[rd]_{\alpha} \\
%& 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \are[dl]_{\delta} \are[dd]^{\beta} \\
1 \are[rd]_{\gamma} \are@/_3pc/[rd]_{\alpha} \\
& 3
}%
%EndExpansion
.
\]
\end{example}
Let us summarize the difference between a simple graph and a multigraph: An
edge of a simple graph $\left( W,E\right) $ is merely a set consisting of
its two endpoints, whereas an edge of a multigraph $\left( W,E,\psi\right) $
can be an arbitrary object (so it \textquotedblleft has its own
identity\textquotedblright) whose endpoints are assigned to it by the map
$\psi$. Thus, we can regard multigraphs as a refined version of simple graphs.
Every simple graph gives rise to a multigraph as follows:
\begin{definition}
Let $\left( W,E\right) $ be a simple graph. Let $\iota:E\rightarrow
\mathcal{P}_{2}\left( W\right) $ be the inclusion map (i.e., the map that
sends each $e\in E$ to $e$ itself); this is well-defined because $E$ is a
subset of $\mathcal{P}_{2}\left( W\right) $ (since $\left( W,E\right) $ is
a simple graph). Then, $\left( W,E,\iota\right) $ is a multigraph. This
multigraph $\left( W,E,\iota\right) $ is called the \textit{multigraph
induced by }$\left( W,E\right) $; we will often just identify it with the
simple graph $\left( W,E\right) $ (so that each simple graph becomes a
multigraph in this way).
\end{definition}
\begin{example}
The simple graph
\[%
%TCIMACRO{\TeXButton{graph on 1,2,3}{\xymatrix{
%& 2 \are[dr] \\
%1 \are[ur] \are[rr] & & 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \are[dr] \\
1 \are[ur] \are[rr] & & 3
}%
%EndExpansion
\]
becomes identified with the multigraph%
\[%
%TCIMACRO{\TeXButton{multigraph on 1,2,3}{\xymatrix{
%& 2 \are[dr]^{\set{2,3}} \\
%1 \are[ur]^{\set{1,2}} \are[rr]_{\set{1,3}} & & 3
%}}}%
%BeginExpansion
\xymatrix{
& 2 \are[dr]^{\set{2,3}} \\
1 \are[ur]^{\set{1,2}} \are[rr]_{\set{1,3}} & & 3
}%
%EndExpansion
\]
in this way.
\end{example}
Both simple graphs and multigraphs are subsumed under the concept of a
\textit{graph}, or, more precisely, \textit{undirected graph}.
\subsection{\label{sect.hall}Bipartite matching and Hall's marriage theorem}
We now define bipartite graphs.
\begin{definition}
\label{def.bipgraph}A \textit{bipartite graph} means a triple $\left(
G;X,Y\right) $ (the semicolon means the same thing as a comma), where
$G=\left( W,E,\psi\right) $ is a multigraph, and where $X$ and $Y$ are two
subsets of $W$ with the following properties:
\begin{itemize}
\item We have $X\cap Y=\varnothing$ and $X\cup Y=W$.
\item Each edge of $G$ contains exactly one vertex in $X$ and exactly one
vertex in $Y$.
\end{itemize}
\end{definition}
For example, if $G$ is the following simple graph:%
\begin{equation}%
%TCIMACRO{\TeXButton{a graph not yet made bipartite}{\xymatrix{
%1 \are[r] \are[d] & 2 \are[d] & 5 \are[d] \\
%4 \are[r] & 3 & 6
%}} }%
%BeginExpansion
\xymatrix{
1 \are[r] \are[d] & 2 \are[d] & 5 \are[d] \\
4 \are[r] & 3 & 6
}
%EndExpansion
\label{eq.bipartite.example1}%
\end{equation}
(regarded as a multigraph)\footnote{Thus, formally speaking, $G$ is the simple
graph whose vertices are $1,2,3,4,5,6$, and whose edges are $\left\{
1,2\right\} ,\left\{ 2,3\right\} ,\left\{ 3,4\right\} ,\left\{
4,1\right\} ,\left\{ 5,6\right\} $.}, then $\left( G;\left\{
1,3,5\right\} ,\left\{ 2,4,6\right\} \right) $ is a bipartite graph, and
$\left( G;\left\{ 2,4,6\right\} ,\left\{ 1,3,5\right\} \right) $ is
another bipartite graph, and $\left( G;\left\{ 1,3,6\right\} ,\left\{
2,4,5\right\} \right) $ is yet another bipartite graph, but $\left(
G;\left\{ 1,2,3\right\} ,\left\{ 4,5,6\right\} \right) $ is not a
bipartite graph (because the edge $\left\{ 1,2\right\} $ of $G$ contains two
vertices in $\left\{ 1,2,3\right\} $, rather than one in $\left\{
1,2,3\right\} $ and one in $\left\{ 4,5,6\right\} $).
We often draw bipartite graphs in a rather special way. Namely, in order to
draw a bipartite graph $\left( G;X,Y\right) $, we draw the graph $G$, but
making sure that all vertices are aligned in two columns, where the left
column contains all the vertices in $X$ and the right column contains all the
vertices in $Y$. For example, if $G$ is the graph shown in
(\ref{eq.bipartite.example1}), then the bipartite graph $\left( G;\left\{
1,3,5\right\} ,\left\{ 2,4,6\right\} \right) $ is drawn as%
\[%
%TCIMACRO{\TeXButton{a bipartite graph}{\xymatrix{
%1 \are[r] \are[rd] & 2 \\
%3 \are[r] \are[ru] & 4 \\
%5 \are[r] & 6
%}}}%
%BeginExpansion
\xymatrix{
1 \are[r] \are[rd] & 2 \\
3 \are[r] \are[ru] & 4 \\
5 \are[r] & 6
}%
%EndExpansion
,
\]
whereas the bipartite graph $\left( G;\left\{ 2,4,6\right\} ,\left\{
1,3,5\right\} \right) $ is drawn as%
\[%
%TCIMACRO{\TeXButton{a bipartite graph}{\xymatrix{
%2 \are[r] \are[rd] & 1 \\
%4 \are[r] \are[ru] & 3 \\
%6 \are[r] & 5
%}}}%
%BeginExpansion
\xymatrix{
2 \are[r] \are[rd] & 1 \\
4 \are[r] \are[ru] & 3 \\
6 \are[r] & 5
}%
%EndExpansion
.
\]
Note that the graph $G$ will be a simple graph in all our examples, but it can
be an arbitrary multigraph in general.
\begin{definition}
Let $G=\left( W,E,\psi\right) $ be a multigraph. A \textit{matching} in $G$
means a subset $M$ of $E$ such that no two distinct edges in $M$ have an
endpoint in common.
\end{definition}
For example, the set $\left\{ \left\{ 1,2\right\} ,\left\{ 5,6\right\}
\right\} $ is a matching in the graph $G$ shown in
(\ref{eq.bipartite.example1}); so is the set $\left\{ \left\{ 1,2\right\}
,\left\{ 3,4\right\} ,\left\{ 5,6\right\} \right\} $ (but not the set
$\left\{ \left\{ 1,2\right\} ,\left\{ 2,3\right\} ,\left\{ 5,6\right\}
\right\} $, because its two edges $\left\{ 1,2\right\} $ and $\left\{
2,3\right\} $ have the endpoint $2$ in common). Also, the empty set
$\varnothing$ is a matching in any graph.
In graph theory, we are often interested in matchings that contain as many
edges as possible. There are, of course, simple bounds on how many edges a
matching can contain: For example, a matching in a multigraph $G=\left(
W,E,\psi\right) $ can never have more than $\left\vert W\right\vert /2$ edges
(since each edge \textquotedblleft uses up\textquotedblright\ two vertices).
Also, if $\left( G;X,Y\right) $ is a bipartite graph, then a matching in $G$
can never have more than $\left\vert X\right\vert $ edges (since each edge
\textquotedblleft uses up\textquotedblright\ a vertex in $X$). How can we find
a maximum-sized matching in $G$ ? This is known as the \textit{bipartite
matching problem} (when $\left( G;X,Y\right) $ is a bipartite graph). It
turns out that the Ford-Fulkerson algorithm (developed in the above proof of
Lemma \ref{lem.3bat}) gives a way to solve this problem in polynomial time.
Let us introduce a couple more concepts:
\begin{definition}
Let $M$ be a matching in a multigraph $G=\left( W,E,\psi\right) $.
\textbf{(a)} A vertex $v$ of $G$ is said to be \textit{matched in $M$} if
there exists an edge $e\in M$ such that $v$ is an endpoint of $e$. In this
case, this edge is unique (since $M$ is a matching), and the other endpoint of
this edge (i.e., the endpoint distinct from $v$) is called the \textit{$M$%
-partner} of $v$.
\textbf{(b)} Let $S$ be a subset of $W$. The matching $M$ is said to be
\textit{$S$-complete} if each vertex $v\in S$ is matched in $M$.
\end{definition}
For example, if $G$ is the graph shown in (\ref{eq.bipartite.example1}), then
the matching $\left\{ \left\{ 1,2\right\} ,\left\{ 3,4\right\} ,\left\{
5,6\right\} \right\} $ is $\left\{ 1,3,6\right\} $-complete (since all
three vertices $1,3,6$ are matched in it\footnote{Their $\left\{ \left\{
1,2\right\} ,\left\{ 3,4\right\} ,\left\{ 5,6\right\} \right\}
$-partners are $2,4,5$, respectively.}), but the matching $\left\{ \left\{
1,2\right\} ,\left\{ 5,6\right\} \right\} $ is not (since the vertex $3$
is not matched in it).
\begin{definition}
Let $G=\left( W,E,\psi\right) $ be a multigraph.
\textbf{(a)} If $v$ is a vertex of $G$, then a \textit{neighbor} of $v$ means
any vertex $w$ of $G$ such that $\left\{ v,w\right\} \in\psi\left(
E\right) $. (Note that the condition $\left\{ v,w\right\} \in\psi\left(
E\right) $ simply says that there exists an edge of $G$ whose endpoints are
$v$ and $w$.)
\textbf{(b)} Let $U$ be a subset of $W$. Then, $N\left( U\right) $ shall
denote the subset%
\[
\left\{ v\in W\ \mid\ v\text{ has a neighbor in }U\right\}
\]
of $W$.
\end{definition}
For example, if $G$ is the graph shown in (\ref{eq.bipartite.example1}), then
the neighbors of the vertex $1$ are $2$ and $4$, and we have $N\left(
\left\{ 1,2\right\} \right) =\left\{ 1,2,3,4\right\} $ and $N\left(
\left\{ 1,3\right\} \right) =\left\{ 2,4\right\} $ and $N\left( \left\{
2,5\right\} \right) =\left\{ 1,3,6\right\} $ and $N\left( \varnothing
\right) =\varnothing$.
The following is almost trivial:
\begin{proposition}
\label{prop.bipartite.NXY}Let $\left( G;X,Y\right) $ be a bipartite graph.
Let $U$ be a subset of $X$. Then, $N\left( U\right) \subseteq Y$.
\end{proposition}
\begin{proof}
[Proof of Proposition \ref{prop.bipartite.NXY}.]Write the multigraph $G$ in
the form $G=\left( W,E,\psi\right) $. Recall that $\left( G;X,Y\right) $
is a bipartite graph; hence, $X\cap Y=\varnothing$ and $X\cup Y=W$. Thus,
$Y=W\setminus X$ and $X=W\setminus Y$.
Now, let $p\in N\left( U\right) $ be arbitrary. Thus, $p\in N\left(
U\right) =\left\{ v\in W\ \mid\ v\text{ has a neighbor in }U\right\} $ (by
the definition of $N\left( U\right) $). In other words, $p$ is an element of
$W$ that has a neighbor in $U$.
The vertex $p$ has a neighbor in $U$. Fix such a neighbor, and denote it by
$q$. Thus, $q\in U\subseteq X=W\setminus Y$, so that $q\notin Y$. We know that
$q$ is a neighbor of $p$; in other words, $\left\{ p,q\right\} \in
\psi\left( E\right) $. In other words, $\left\{ p,q\right\} =\psi\left(
e\right) $ for some $e\in E$. Consider this $e$. Thus, $e$ is an edge of $G$
(since $e\in E$), and has endpoints $p$ and $q$ (since $\left\{ p,q\right\}
=\psi\left( e\right) $).
But $\left( G;X,Y\right) $ is a bipartite graph. Hence, each edge of $G$
contains exactly one vertex in $X$ and exactly one vertex in $Y$. Thus, in
particular, each edge of $G$ contains a vertex in $Y$. Applying this to the
edge $e$, we conclude that the edge $e$ contains a vertex in $Y$. In other
words, one of the two endpoints of $e$ lies in $Y$. In other words, one of the
two vertices $p$ and $q$ lies in $Y$ (since the endpoints of $e$ are $p$ and
$q$). This vertex cannot be $q$ (since $q\notin Y$), and thus must be $p$.
Hence, $p$ lies in $Y$. In other words, $p\in Y$.
Now, forget that we fixed $p$. We have thus shown that $p\in Y$ for each $p\in
N\left( U\right) $. In other words, $N\left( U\right) \subseteq Y$. This
proves Proposition \ref{prop.bipartite.NXY}.
\end{proof}
We shall now study matchings in bipartite graphs. The most important result
about such matchings is the following fact, known as \textit{Hall's marriage
theorem}:
\begin{theorem}
\label{thm.hall}Let $\left( G;X,Y\right) $ be a bipartite graph. Then, $G$
has an $X$-complete matching if and only if each subset $U$ of $X$ satisfies
$\left\vert N\left( U\right) \right\vert \geq\left\vert U\right\vert $.
\end{theorem}
Theorem \ref{thm.hall} has applications throughout mathematics, and several
equivalent versions; it also has fairly elementary (but tricky) proofs (see,
e.g., \cite[\S 12.5.2]{LeLeMe17}). We shall derive it from Theorem
\ref{thm.3b}.
In order to do so (and also, in order to reduce the bipartite matching problem
to the Ford-Fulkerson algorithm), we need to construct a network from a given
bipartite graph such that the integer flows in the network shall correspond to
the matchings in the graph. Let us do this.
\begin{condition}
For the rest of Section \ref{sect.hall}, we fix a bipartite graph $\left(
G;X,Y\right) $. Write the multigraph $G$ in the form $G=\left(
W,E,\psi\right) $.
\end{condition}
We know that $\left( G;X,Y\right) $ is a bipartite graph. Thus, each edge of
$G$ contains exactly one vertex in $X$ and exactly one vertex in $Y$. In other
words, if $e$ is an edge of $G$, then exactly one endpoint of $e$ lies in $X$,
and exactly one endpoint of $e$ lies in $Y$.
Now, we shall construct a network $N$ out of our bipartite graph $\left(
G;X,Y\right) $. Before we give the rigorous definition, let us show it on an
example:\newpage
\begin{example}
\label{exa.hall.network.1}For this example, let $G=\left( W,E\right) $ be
the simple graph with vertices $1,2,3,4,5,6,7$ and edges $\left\{
1,4\right\} ,\left\{ 1,5\right\} ,\left\{ 2,4\right\} ,\left\{
2,7\right\} ,\left\{ 3,5\right\} ,\left\{ 3,6\right\} $. Set $X=\left\{
1,2,3\right\} $ and $Y=\left\{ 4,5,6,7\right\} $; then, $\left(
G;X,Y\right) $ is a bipartite graph which can be drawn as follows:%
\[%
%TCIMACRO{\TeXButton{a bipartite graph}{\xymatrix@C=5pc{
%1 \are[r] \are[rd] & 4 \\
%2 \are[ru] \are[rdd] & 5 \\
%3 \are[ru] \are[r] & 6 \\
%& 7
%}}}%
%BeginExpansion
\xymatrix@C=5pc{
1 \are[r] \are[rd] & 4 \\
2 \are[ru] \are[rdd] & 5 \\
3 \are[ru] \are[r] & 6 \\
& 7
}%
%EndExpansion
.
\]
Regard $G$ as a multigraph. Now, we shall transform this multigraph $G$ into a
multidigraph by replacing each edge $e$ by an arc $\overrightarrow{e}$. The
source of this arc $\overrightarrow{e}$ shall be the unique endpoint of $e$
that lies in $X$; the target of this arc $\overrightarrow{e}$ shall be the
unique endpoint of $e$ that lies in $Y$. Thus, our multigraph $G$ has been
transformed into the following multidigraph:%
\[%
%TCIMACRO{\TeXButton{a bipartite graph with directed arcs}{\xymatrix@C=5pc{
%1 \ar[r] \ar[rd] & 4 \\
%2 \ar[ru] \ar[rdd] & 5 \\
%3 \ar[ru] \ar[r] & 6 \\
%& 7
%}}}%
%BeginExpansion
\xymatrix@C=5pc{
1 \ar[r] \ar[rd] & 4 \\
2 \ar[ru] \ar[rdd] & 5 \\
3 \ar[ru] \ar[r] & 6 \\
& 7
}%
%EndExpansion
\]
(where we are omitting the labels on the arcs). The arcs of this multidigraph
will be called the $G$\textit{-arcs} (to stress that they come directly from
the edges of $G$, as opposed to the next arcs that we are going to add).
Next, we add a new vertex, which we call $s$ and which we draw on the very
left. This $s$ will be the source of our network. For each $x\in X$, we add an
arc $\left( s,x\right) $ to our multidigraph; this arc shall have source $s$
and target $x$. These new arcs (a total of $\left\vert X\right\vert $ arcs,
one for each $x\in X$) will be called the $s$\textit{-arcs}. Here is how our
multidigraph now looks like:%
\[%
%TCIMACRO{\TeXButton{a bipartite graph with directed arcs and s}{\xymatrix@C
%=5pc{
%& 1 \ar[r] \ar[rd] & 4 \\
%s \ar[ru] \ar[r] \ar[rd] & 2 \ar[ru] \ar[rdd] & 5 \\
%& 3 \ar[ru] \ar[r] & 6 \\
%& & 7
%}}}%
%BeginExpansion
\xymatrix@C=5pc{
& 1 \ar[r] \ar[rd] & 4 \\
s \ar[ru] \ar[r] \ar[rd] & 2 \ar[ru] \ar[rdd] & 5 \\
& 3 \ar[ru] \ar[r] & 6 \\
& & 7
}%
%EndExpansion
.
\]
Next, we add a new vertex, which we call $t$ and which we draw on the very
right. This $t$ will be the sink of our network. For each $y\in Y$, we add an
arc $\left( y,t\right) $ to our multidigraph; this arc shall have source $y$
and target $t$. These new arcs (a total of $\left\vert Y\right\vert $ arcs,
one for each $y\in Y$) will be called the $t$\textit{-arcs}. Here is how our
multidigraph now looks like:%
\[%
%TCIMACRO{\TeXButton{a bipartite graph with directed arcs and s and
%t}{\xymatrix@C=5pc{
%& 1 \ar[r] \ar[rd] & 4 \ar[rd] \\
%s \ar[ru] \ar[r] \ar[rd] & 2 \ar[ru] \ar[rdd] & 5 \ar[r] & t \\
%& 3 \ar[ru] \ar[r] & 6 \ar[ru] \\
%& & 7 \ar[ruu]
%}}}%
%BeginExpansion
\xymatrix@C=5pc{
& 1 \ar[r] \ar[rd] & 4 \ar[rd] \\
s \ar[ru] \ar[r] \ar[rd] & 2 \ar[ru] \ar[rdd] & 5 \ar[r] & t \\
& 3 \ar[ru] \ar[r] & 6 \ar[ru] \\
& & 7 \ar[ruu]
}%
%EndExpansion
.
\]
This $9$-vertex multidigraph will be the underlying multidigraph of our
network $N$. The source and the target of $N$ shall be $s$ and $t$,
respectively. The capacity function $c$ is determined by setting $c\left(
a\right) =1$ for each arc of the network.
We claim that the integer flows on the network $N$ are in bijection with the
matchings in $G$. Again, let us show how this bijection acts on an example.
Consider the following integer flow on $N$:%
\begin{equation}%
%TCIMACRO{\TeXButton{an integer flow on N}{\xymatrix@C=5pc{
%& 1 \ar[r] \ar[rd] & 4 \ar@{=>}[rd] \\
%s \ar[ru] \ar@{=>}[r] \ar@{=>}[rd] & 2 \ar@{=>}[ru] \ar[rdd] & 5 \ar[r] & t \\
%& 3 \ar[ru] \ar@{=>}[r] & 6 \ar@{=>}[ru] \\
%& & 7 \ar[ruu]
%}}}%
%BeginExpansion
\xymatrix@C=5pc{
& 1 \ar[r] \ar[rd] & 4 \ar@{=>}[rd] \\
s \ar[ru] \ar@{=>}[r] \ar@{=>}[rd] & 2 \ar@{=>}[ru] \ar[rdd] & 5 \ar[r] & t \\
& 3 \ar[ru] \ar@{=>}[r] & 6 \ar@{=>}[ru] \\
& & 7 \ar[ruu]
}%
%EndExpansion
, \label{eq.exam.hall.bij1}%
\end{equation}
where a simple arrow ($\longrightarrow$) stands for an arc which the flow
sends to $0$, and where a double arrow ($\Longrightarrow$) stands for an arc
which the flow sends to $1$. (This is just an alternative way of drawing an
integer flow when each arc has capacity $1$.) Consider the arcs that are sent
to $1$ by this flow. Two of these arcs are $G$-arcs, namely
$\overrightarrow{\left\{ 2,4\right\} }$ and $\overrightarrow{\left\{
3,6\right\} }$. The corresponding edges $\left\{ 2,4\right\} $ and
$\left\{ 3,6\right\} $ of $G$ form a matching: the matching $\left\{
\left\{ 2,4\right\} ,\left\{ 3,6\right\} \right\} $. This matching has
size $2$, which is exactly the value of our integer flow.
\end{example}
Let us now formalize what we did in this example. First, here is the general
definition of the network $N$:
\begin{definition}
\label{def.hall.network}\textbf{(a)} Pick two distinct new objects $s$ and
$t$. Let $V$ be the finite set $W\cup\left\{ s,t\right\} $.
The elements of $V$ will be the vertices of our network, with $s$ being the
source and $t$ being the sink.
Next, we shall introduce three sets $A_{s}$, $A_{t}$ and $A_{G}$, whose
elements will be the arcs of our network. (More precisely, the elements of
$A_{G}$ will be the $G$-arcs, the elements of $A_{s}$ will be the $s$-arcs,
and the elements of $A_{t}$ be the $t$-arcs.)
\textbf{(b)} Define two finite sets $A_{s}$ and $A_{t}$ by%
\begin{align*}
A_{s} & =\left\{ s\right\} \times X=\left\{ \left( s,x\right)
\ \mid\ x\in X\right\} \ \ \ \ \ \ \ \ \ \ \text{and}\\
A_{t} & =Y\times\left\{ t\right\} =\left\{ \left( y,t\right)
\ \mid\ y\in Y\right\} .
\end{align*}
Note that $A_{s}$ and $A_{t}$ are disjoint (since each element of $A_{s}$ is a
pair whose first entry is $s$, whereas no element of $A_{t}$ has this property).
\textbf{(c)} For each edge $e\in E$, we let $\overrightarrow{e}$ be the triple
$\left( x,y,e\right) $, where $x$ is the unique endpoint of $e$ that lies in
$X$, and where $y$ is the unique endpoint of $e$ that lies in $Y$. (Here, we
are using the fact that exactly one endpoint of $e$ lies in $X$, and exactly
one endpoint of $e$ lies in $Y$.) Note that the triples $\overrightarrow{e}$
for $e\in E$ are pairwise distinct (i.e., if two edges $e$ and $f$ satisfy
$e\neq f$, then $\overrightarrow{e}\neq\overrightarrow{f}$), because the third
entry of the triple $\overrightarrow{e}$ is always the original edge $e\in E$.
\textbf{(d)} Define a finite set $A_{G}$ by%
\[
A_{G}=\left\{ \overrightarrow{e}\ \mid\ e\in E\right\} .
\]
Thus, the set $A_{G}$ is in bijection with $E$ (since the triples
$\overrightarrow{e}$ for $e\in E$ are pairwise distinct), and is disjoint from
both $A_{s}$ and $A_{t}$ (because the elements of $A_{G}$ are triples, while
the elements of $A_{s}$ and of $A_{t}$ are pairs).
\textbf{(e)} Let $A$ be the union $A_{G}\cup A_{s}\cup A_{t}$; this is a
finite set. Define a map $\phi:A\rightarrow V\times V$ by the following three
equalities%
\begin{align*}
\phi\left( \left( x,y,e\right) \right) & =\left( x,y\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }\left( x,y,e\right) \in A_{G};\\
\phi\left( \left( s,x\right) \right) & =\left( s,x\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }\left( s,x\right) \in A_{s};\\
\phi\left( \left( y,t\right) \right) & =\left( y,t\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }\left( y,t\right) \in A_{t}.
\end{align*}
Thus, $\left( V,A,\phi\right) $ is a multidigraph. The elements of $A_{G}$
shall be called the $G$\textit{-arcs}; the elements of $A_{s}$ shall be called
the $s$\textit{-arcs}; the elements of $A_{t}$ shall be called the
$t$\textit{-arcs}. Thus, the arcs of the multidigraph $\left( V,A,\phi
\right) $ are the $G$-arcs, the $s$-arcs and the $t$-arcs.
\textbf{(f)} Define the function $c:A\rightarrow\mathbb{Q}_{+}$ by $\left(
c\left( a\right) =1\text{ for each }a\in A\right) $. Thus, $c$ is a
constant function.
\textbf{(g)} Let $N$ be the network consisting of the multidigraph $\left(
V,A,\phi\right) $, the source $s$, the sink $t$ and the capacity function $c$.
\end{definition}
As we have seen, the sets $A_{G}$, $A_{s}$ and $A_{t}$ are mutually disjoint;
i.e., there is no overlap between the $G$-arcs, the $s$-arcs and the $t$-arcs.
All $s$-arcs have source $s$, whereas none of the other types of arcs do.
Likewise, all $t$-arcs have target $t$, whereas none of the other types of
arcs do. The $G$-arcs have their sources lie in $X$ and their targets lie in
$Y$.
We notice that each $s$-arc is literally the pair of its source and its
target, as in a simple digraph. The same is true for the $t$-arcs. However,
the $G$-arcs are not pairs; thus, $\left( V,A,\phi\right) $ is not a simple digraph.
\begin{noncompile}
This is essentially obvious (for example, all $s$-arcs have source $s$,
whereas none of the other types of arcs do; likewise, all $t$-arcs have target
$t$, whereas none of the other types of arcs do).
\end{noncompile}
Our specific choice of capacity function $c$ ensures that integer flows on $N$
have a very simple form: If $f$ is an integer flow on $N$, and if $a\in A$ is
any arc, then $f\left( a\right) $ is either $0$ or $1$. (Indeed, $f\left(
a\right) $ must be an integer since $f$ is an integer flow; but the capacity
constraints enforce $0\leq f\left( a\right) \leq1$, so that this integer
$f\left( a\right) $ must be either $0$ or $1$.) Thus, an integer flow $f$ on
$N$ is uniquely determined by knowing which of the arcs $a\in A$ it sends to
$1$ (because then, it has to send all the other arcs to $0$).
Another consequence of our definition of capacity function $c$ is the following:
\begin{lemma}
\label{lem.hall.cPQ}Let $P$ and $Q$ be two subsets of $V$. Then, $c\left(
P,Q\right) =\left\vert \left[ P,Q\right] \right\vert $.
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.hall.cPQ}.]The definition of $c\left( P,Q\right) $
yields%
\[
c\left( P,Q\right) =\sum_{a\in\left[ P,Q\right] }\underbrace{c\left(
a\right) }_{\substack{=1\\\text{(by the definition of }c\text{)}}}=\sum
_{a\in\left[ P,Q\right] }1=\left\vert \left[ P,Q\right] \right\vert
\cdot1=\left\vert \left[ P,Q\right] \right\vert .
\]
This proves Lemma \ref{lem.hall.cPQ}.
\end{proof}
Now, we want to formulate the bijection between integer flows on $N$ and
matchings in $G$. First, we need a simple property of integer flows on our
specific network $N$:\ \ \ \ \footnote{We are using the \textit{Iverson
bracket notation}: If $\mathcal{A}$ is any logical statement, then $\left[
\mathcal{A}\right] $ denotes the integer $%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
$.}
\begin{proposition}
\label{prop.hall.lem1}Let $f$ be any integer flow on $N$. Let $M$ be the
subset $\left\{ e\in E\ \mid\ f\left( \overrightarrow{e}\right) =1\right\}
$ of $E$.
\textbf{(a)} We have $f\left( \left( s,x\right) \right) =\sum
_{\substack{e\in E;\\x\in e}}f\left( \overrightarrow{e}\right) $ for each
$x\in X$.
\textbf{(b)} We have $f\left( \left( y,t\right) \right) =\sum
_{\substack{e\in E;\\y\in e}}f\left( \overrightarrow{e}\right) $ for each
$y\in Y$.
\textbf{(c)} We have $M=\left\{ e\ \mid\ \left( x,y,e\right) \in
A_{G};\ f\left( \left( x,y,e\right) \right) =1\right\} $.
\textbf{(d)} The set $M=\left\{ e\in E\ \mid\ f\left( \overrightarrow{e}%
\right) =1\right\} $ is a matching in $G$.
\textbf{(e)} We have $\left\vert M\right\vert =\left\vert f\right\vert $.
\textbf{(f)} For any vertex $x\in X$, we have $\left[ x\text{ is matched in
}M\right] =f\left( \left( s,x\right) \right) $.
\textbf{(g)} For any vertex $y\in Y$, we have $\left[ y\text{ is matched in
}M\right] =f\left( \left( y,t\right) \right) $.
\end{proposition}
For example, if $f$ is the flow shown in (\ref{eq.exam.hall.bij1}), then the
set $M$ in Proposition \ref{prop.hall.lem1} is the matching $\left\{ \left\{
2,4\right\} ,\left\{ 3,6\right\} \right\} $ in $G$.
\begin{proof}
[Proof of Proposition \ref{prop.hall.lem1} (sketched).]We shall only prove the
parts of Proposition \ref{prop.hall.lem1} used in the below proof of Theorem
\ref{thm.hall} (namely, parts \textbf{(a)}, \textbf{(b)}, \textbf{(d)} and
\textbf{(e)}); the rest is left to the reader.
We first make the following observations:
\begin{statement}
\textit{Observation 1:} Let $x\in X$ and $e\in E$. Then, the arc
$\overrightarrow{e}$ has source $x$ if and only if $x\in e$.
\end{statement}
[\textit{Proof of Observation 1:} Recall that $\left( G;X,Y\right) $ is a
bipartite graph. Thus, exactly one endpoint of $e$ lies in $X$, and exactly
one endpoint of $e$ lies in $Y$. Let $u$ be the unique endpoint of $e$ that
lies in $X$, and let $v$ be the unique endpoint of $e$ that lies in $Y$. Then,
$\overrightarrow{e}=\left( u,v,e\right) $ (by the definition of
$\overrightarrow{e}$). Hence, $\phi\left( \overrightarrow{e}\right)
=\phi\left( \left( u,v,e\right) \right) =\left( u,v\right) $ (by the
definition of $\phi$). In other words, the source of the arc
$\overrightarrow{e}$ is $u$, and the target of the arc $\overrightarrow{e}$ is
$v$.
We now shall prove the $\Longrightarrow$ and $\Longleftarrow$ directions of
Observation 1 separately:
$\Longrightarrow:$ Assume that the arc $\overrightarrow{e}$ has source $x$. We
must prove that $x\in e$.
The arc $\overrightarrow{e}$ has source $x$. In other words, the source of the
arc $\overrightarrow{e}$ is $x$. In other words, $u=x$ (since the source of
the arc $\overrightarrow{e}$ is $u$). But $u$ is an endpoint of $e$; thus,
$u\in e$. Hence, $x=u\in e$. This proves the $\Longrightarrow$ direction of
Observation 1.
$\Longleftarrow:$ Assume that $x\in e$. We must show that the arc
$\overrightarrow{e}$ has source $x$.
Recall that $u$ is the unique endpoint of $e$ that lies in $X$. The vertex $x$
is an endpoint of $e$ (since $x\in e$) and lies in $X$ (since $x\in X$). Thus,
the unique endpoint of $e$ that lies in $X$ must be $x$. In other words, $u$
must be $x$ (since $u$ is the unique endpoint of $e$ that lies in $X$). Thus,
$u=x$. Now, the source of the arc $\overrightarrow{e}$ is $u=x$. In other
words, the arc $\overrightarrow{e}$ has source $x$. Thus, the $\Longleftarrow$
direction of Observation 1 is proven.]
\begin{statement}
\textit{Observation 2:} Let $y\in Y$ and $e\in E$. Then, the arc
$\overrightarrow{e}$ has target $y$ if and only if $y\in e$.
\end{statement}
[\textit{Proof of Observation 2:} Analogous to Observation 1.]
\begin{statement}
\textit{Observation 3:} The arcs $\overrightarrow{e}$ for $e\in E$ are
pairwise distinct.
\end{statement}
[\textit{Proof of Observation 3:} We have already shown this in Definition
\ref{def.hall.network} \textbf{(c)}.]
Now, we observe that $s\notin W$, so that $s\notin X$ and $s\notin Y$. Also,
$X\cap Y=\varnothing$ (since $\left( G;X,Y\right) $ is a bipartite graph),
so that $X\subseteq V\setminus Y$.
\begin{statement}
\textit{Observation 4:} Let $x\in X$. Then, the arcs $a\in A$ having source
$x$ are exactly the arcs $\overrightarrow{e}$ for $e\in E$ satisfying $x\in e$.
\end{statement}
[\textit{Proof of Observation 4:} We have $x\in X$ but $s\notin X$ (since
$s\notin W$). Thus, $x\neq s$. Hence, there are no $s$-arcs having source $x$
(since all $s$-arcs have source $s\neq x$). Also, $x\notin Y$ (since $x\in
X\subseteq V\setminus Y$). Thus, there are no $t$-arcs having source $x$
(since all $t$-arcs have source lying in $Y$).
Recall that there are three types of arcs $a\in A$: the $G$-arcs, the $s$-arcs
and the $t$-arcs. Among these three types, only $G$-arcs can have source $x$
(because we have seen that there are no $s$-arcs having source $x$, and that
there are no $t$-arcs having source $x$). Hence,%
\begin{align*}
& \left\{ \text{the arcs }a\in A\text{ having source }x\right\} \\
& =\left\{ \text{the }G\text{-arcs having source }x\right\} \\
& =\left\{ \text{the arcs }\overrightarrow{e}\text{ (with }e\in E\text{)
having source }x\right\} \\
& \ \ \ \ \ \ \ \ \ \ \left( \text{since the }G\text{-arcs are precisely the
arcs }\overrightarrow{e}\text{ (with }e\in E\text{)}\right) \\
& =\left\{ \overrightarrow{e}\ \mid\ e\in E;\ \underbrace{\text{the arc
}\overrightarrow{e}\text{ has source }x}_{\substack{\Longleftrightarrow
\ \left( x\in e\right) \\\text{(by Observation 1)}}}\right\} \\
& =\left\{ \overrightarrow{e}\ \mid\ e\in E;\ x\in e\right\} =\left\{
\text{the arcs }\overrightarrow{e}\text{ for }e\in E\text{ satisfying }x\in
e\right\} .
\end{align*}
In other words, the arcs $a\in A$ having source $x$ are exactly the arcs
$\overrightarrow{e}$ for $e\in E$ satisfying $x\in e$. This proves Observation 4.]
\begin{statement}
\textit{Observation 5:} Let $y\in Y$. Then, the arcs $a\in A$ having target
$y$ are exactly the arcs $\overrightarrow{e}$ for $e\in E$ satisfying $y\in e$.
\end{statement}
[\textit{Proof of Observation 5:} Analogous to Observation 4.]
\begin{statement}
\textit{Observation 6:} Let $x\in X$. Then, there is a unique arc $a\in A$
having target $x$, namely the $s$-arc $\left( s,x\right) $.
\end{statement}
[\textit{Proof of Observation 6:} We have $x\in X\subseteq W$ but $t\notin W$.
Thus, $x\neq t$. Hence, there are no $t$-arcs having target $x$ (since all
$t$-arcs have target $t\neq x$). Also, $x\notin Y$ (since $x\in X\subseteq
V\setminus Y$). Thus, there are no $G$-arcs having target $x$ (since all
$G$-arcs have target lying in $Y$).
Recall that there are three types of arcs $a\in A$: the $G$-arcs, the $s$-arcs
and the $t$-arcs. Among these three types, only $s$-arcs can have target $x$
(because we have seen that there are no $t$-arcs having target $x$, and that
there are no $G$-arcs having target $x$). Hence,%
\[
\left\{ \text{the arcs }a\in A\text{ having target }x\right\} =\left\{
\text{the }s\text{-arcs having target }x\right\} .
\]
But the $s$-arcs are simply the pairs of the form $\left( s,x^{\prime
}\right) $ for all $x^{\prime}\in X$ (by the definition of the $s$-arcs), and
their respective targets are $x^{\prime}$. Thus, there is a unique $s$-arc
having target $x$, namely $\left( s,x\right) $ (since $x\in X$). In other
words, $\left\{ \text{the }s\text{-arcs having target }x\right\} =\left\{
\left( s,x\right) \right\} $. Hence,%
\[
\left\{ \text{the arcs }a\in A\text{ having target }x\right\} =\left\{
\text{the }s\text{-arcs having target }x\right\} =\left\{ \left(
s,x\right) \right\} .
\]
In other words, there is a unique arc $a\in A$ having target $x$, namely the
$s$-arc $\left( s,x\right) $. This proves Observation 6.]
\begin{statement}
\textit{Observation 7:} Let $y\in Y$. Then, there is a unique arc $a\in A$
having source $y$, namely the $t$-arc $\left( y,t\right) $.
\end{statement}
[\textit{Proof of Observation 7:} Analogous to Observation 6.]
\begin{statement}
\textit{Observation 8:} The arcs $a\in A$ having source $s$ are exactly the
arcs $\left( s,x\right) $ for $x\in X$, and these arcs are pairwise distinct.
\end{statement}
[\textit{Proof of Observation 8:} We have $s\notin W$ and thus $s\notin X$
(since $X\subseteq W$). Hence, there are no $G$-arcs having source $s$ (since
all $G$-arcs have source lying in $X$). Also, $s\notin W$ and thus $s\notin Y$
(since $Y\subseteq W$). Thus, there are no $t$-arcs having source $s$ (since
all $t$-arcs have source lying in $Y$).
Recall that there are three types of arcs $a\in A$: the $G$-arcs, the $s$-arcs
and the $t$-arcs. Among these three types, only $s$-arcs can have source $s$
(because we have seen that there are no $G$-arcs having source $s$, and that
there are no $t$-arcs having source $s$). Hence,%
\begin{align*}
& \left\{ \text{the arcs }a\in A\text{ having source }s\right\} \\
& =\left\{ \text{the }s\text{-arcs having source }s\right\} \\
& =\left\{ \text{the }s\text{-arcs}\right\} \ \ \ \ \ \ \ \ \ \ \left(
\text{since \textbf{all} }s\text{-arcs have source }s\right) \\
& =A_{s}=\left\{ \left( s,x\right) \ \mid\ x\in X\right\} .
\end{align*}
In other words, the arcs $a\in A$ having source $s$ are exactly the arcs
$\left( s,x\right) $ for $x\in X$. Furthermore, these arcs are pairwise
distinct (since the targets $x$ of these arcs are pairwise distinct). This
proves Observation 8.]
\begin{statement}
\textit{Observation 9:} There are no arcs $a\in A$ having target $s$.
\end{statement}
[\textit{Proof of Observation 9:} We have $s\notin W$ and thus $s\notin X$
(since $X\subseteq W$). Hence, there are no $s$-arcs having target $s$ (since
all $s$-arcs have target lying in $X$). Also, $s\notin W$ and thus $s\notin Y$
(since $Y\subseteq W$). Hence, there are no $G$-arcs having target $s$ (since
all $G$-arcs have target lying in $Y$). Finally, $s\neq t$. Thus, there are no
$t$-arcs having target $s$ (since all $t$-arcs have target $t\neq s$).
Recall that there are three types of arcs $a\in A$: the $G$-arcs, the $s$-arcs
and the $t$-arcs. Among these three types, none can have target $s$ (since we
have seen that there are no $G$-arcs having target $s$, no $s$-arcs having
target $s$, and no $t$-arcs having target $s$). Thus, there are no arcs $a\in
A$ having target $s$. This proves Observation 9.]
Recall that $f$ is a flow; thus, $f$ satisfies the capacity constraints and
the conservation constraints.
\textbf{(a)} Let $x\in X$. Then, $x\in X\subseteq W=V\setminus\left\{
s,t\right\} $. Hence, $f^{-}\left( x\right) =f^{+}\left( x\right) $
(since $f$ satisfies the conservation constraints).
Observation 6 shows that there is a unique arc $a\in A$ having target $x$,
namely the $s$-arc $\left( s,x\right) $. Thus, $\sum_{\substack{a\in A\text{
is an arc}\\\text{with target }x}}f\left( a\right) =f\left( \left(
s,x\right) \right) $.
The definition of $f^{-}\left( x\right) $ yields
\begin{equation}
f^{-}\left( x\right) =\sum_{\substack{a\in A\text{ is an arc}\\\text{with
target }x}}f\left( a\right) =f\left( \left( s,x\right) \right) .
\label{pf.prop.hall.lem1.a.f-}%
\end{equation}
Observation 4 shows that the arcs $a\in A$ having source $x$ are exactly the
arcs $\overrightarrow{e}$ for $e\in E$ satisfying $x\in e$. Since these arcs
$\overrightarrow{e}$ are pairwise distinct (by Observation 3), we thus
conclude that $\sum_{\substack{a\in A\text{ is an arc}\\\text{with source }%
x}}f\left( a\right) =\sum_{\substack{e\in E;\\x\in e}}f\left(
\overrightarrow{e}\right) $.
The definition of $f^{+}\left( x\right) $ yields%
\begin{equation}
f^{+}\left( x\right) =\sum_{\substack{a\in A\text{ is an arc}\\\text{with
source }x}}f\left( a\right) =\sum_{\substack{e\in E;\\x\in e}}f\left(
\overrightarrow{e}\right) . \label{pf.prop.hall.lem1.a.f+}%
\end{equation}
Now, recall that $f^{-}\left( x\right) =f^{+}\left( x\right) $. In view of
(\ref{pf.prop.hall.lem1.a.f-}) and (\ref{pf.prop.hall.lem1.a.f+}), this
rewrites as $f\left( \left( s,x\right) \right) =\sum_{\substack{e\in
E;\\x\in e}}f\left( \overrightarrow{e}\right) $. This proves Proposition
\ref{prop.hall.lem1} \textbf{(a)}.
\textbf{(b)} The proof of Proposition \ref{prop.hall.lem1} \textbf{(b)} is
analogous to that of Proposition \ref{prop.hall.lem1} \textbf{(a)}.
\textbf{(d)} Clearly, $M=\left\{ e\in E\ \mid\ f\left( \overrightarrow{e}%
\right) =1\right\} $ is a subset of $E$. We must prove that this subset $M$
is a matching in $G$. Since we already know that $M$ is a subset of $E$, we
only need to verify that no two distinct edges in $M$ have an endpoint in
common (by the definition of a matching).
Let us assume the contrary. Thus, there exist two distinct edges $g$ and $h$
in $M$ that have an endpoint in common. Consider such $g$ and $h$.
The edges $g$ and $h$ have an endpoint in common. In other words, there exists
a $w\in W$ such that $w\in g$ and $w\in h$. Consider this $w$.
We have $g\in M\subseteq E$ and $w\in g$. Thus, $g$ is an edge $e\in E$
satisfying $w\in e$. Similarly, $h$ is an edge $e\in E$ satisfying $w\in e$.
From $g\in M=\left\{ e\in E\ \mid\ f\left( \overrightarrow{e}\right)
=1\right\} $, we conclude that $f\left( \overrightarrow{g}\right) =1$.
Similarly, $f\left( \overrightarrow{h}\right) =1$.
We have $w\in W=X\cup Y$ (since $\left( G;X,Y\right) $ is a bipartite
graph); thus, we have either $w\in X$ or $w\in Y$. So we are in one of the
following two cases:
\begin{statement}
\textit{Case 1:} We have $w\in X$.
\end{statement}
\begin{statement}
\textit{Case 2:} We have $w\in Y$.
\end{statement}
Let us consider Case 1. In this case, we have $w\in X$. Proposition
\ref{prop.hall.lem1} \textbf{(a)} (applied to $x=w$) thus yields%
\begin{align*}
f\left( \left( s,w\right) \right) & =\sum_{\substack{e\in E;\\w\in
e}}f\left( \overrightarrow{e}\right) =\underbrace{f\left(
\overrightarrow{g}\right) }_{=1}+\underbrace{f\left( \overrightarrow{h}%
\right) }_{=1}+\sum_{\substack{e\in E;\\w\in e;\\e\notin\left\{ g,h\right\}
}}\underbrace{f\left( \overrightarrow{e}\right) }_{\substack{\geq
0\\\text{(since }f\text{ is a map }A\rightarrow\mathbb{Q}_{+}\text{)}}}\\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addends for }e=g\text{ and }e=h\text{,}\\
\text{since }g\text{ and }h\text{ are two distinct edges }e\in E\text{
satisfying }w\in e
\end{array}
\right) \\
& \geq1+1+\sum_{\substack{e\in E;\\w\in e;\\e\notin\left\{ g,h\right\}
}}0=2.
\end{align*}
But recall that $f$ satisfies the capacity constraints. Thus, $0\leq f\left(
a\right) \leq c\left( a\right) $ for each arc $a\in A$. Applying this to
$a=\left( s,w\right) $, we conclude that $0\leq f\left( \left( s,w\right)
\right) \leq c\left( \left( s,w\right) \right) $. Hence, $f\left(
\left( s,w\right) \right) \leq c\left( \left( s,w\right) \right) =1$
(by the definition of $c$). This contradicts $f\left( \left( s,w\right)
\right) \geq2>1$. Thus, we have found a contradiction in Case 1.
Similarly, we obtain a contradiction in Case 2 (using Proposition
\ref{prop.hall.lem1} \textbf{(b)} instead of Proposition \ref{prop.hall.lem1}
\textbf{(a)}).
Hence, we have found a contradiction in both Cases 1 and 2. Thus, we always
get a contradiction. This completes our proof that $M$ is a matching in $G$.
Thus, Proposition \ref{prop.hall.lem1} \textbf{(d)} is established.
\textbf{(e)} For any edge $e\in E$, we have either $f\left(
\overrightarrow{e}\right) =0$ or $f\left( \overrightarrow{e}\right)
=1$\ \ \ \ \footnote{\textit{Proof.} Let $e\in E$. Then, $\overrightarrow{e}$
is an arc in $A$ (namely, a $G$-arc). But recall that $f$ satisfies the
capacity constraints. Thus, $0\leq f\left( a\right) \leq c\left( a\right)
$ for each arc $a\in A$. Applying this to $a=\overrightarrow{e}$, we conclude
that $0\leq f\left( \overrightarrow{e}\right) \leq c\left(
\overrightarrow{e}\right) $. Hence, $f\left( \overrightarrow{e}\right) \leq
c\left( \overrightarrow{e}\right) =1$ (by the definition of $c$). Thus,
$0\leq f\left( \overrightarrow{e}\right) \leq1$.
\par
But $f$ is an integer flow; thus, $f\left( \overrightarrow{e}\right) $ is an
integer. Combining this with $0\leq f\left( \overrightarrow{e}\right) \leq
1$, we conclude that $f\left( \overrightarrow{e}\right) \in\left\{
0,1\right\} $. In other words, either $f\left( \overrightarrow{e}\right)
=0$ or $f\left( \overrightarrow{e}\right) =1$. Qed.}.
Observation 8 shows that the arcs $a\in A$ having source $s$ are exactly the
arcs $\left( s,x\right) $ for $x\in X$, and these arcs are pairwise
distinct. Hence,%
\begin{align}
\sum_{\substack{a\in A\text{ is an arc}\\\text{with source }s}}f\left(
a\right) & =\sum_{x\in X}\underbrace{f\left( \left( s,x\right) \right)
}_{\substack{=\sum_{\substack{e\in E;\\x\in e}}f\left( \overrightarrow{e}%
\right) \\\text{(by Proposition \ref{prop.hall.lem1} \textbf{(a)})}%
}}=\underbrace{\sum_{x\in X}\sum_{\substack{e\in E;\\x\in e}}}_{=\sum_{e\in
E}\sum_{\substack{x\in X;\\x\in e}}}f\left( \overrightarrow{e}\right)
\nonumber\\
& =\sum_{e\in E}\sum_{\substack{x\in X;\\x\in e}}f\left( \overrightarrow{e}%
\right) . \label{pf.prop.hall.lem1.e.1}%
\end{align}
But each $e\in E$ satisfies
\begin{equation}
\sum_{\substack{x\in X;\\x\in e}}f\left( \overrightarrow{e}\right) =f\left(
\overrightarrow{e}\right) \label{pf.prop.hall.lem1.e.2}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.hall.lem1.e.2}):} Let $e\in E$. Each
edge of $G$ contains exactly one vertex in $X$ and exactly one vertex in $Y$
(since $\left( G;X,Y\right) $ is a bipartite graph). Thus, in particular,
each edge of $G$ contains exactly one vertex in $X$. Applying this to the edge
$e$, we conclude that $e$ contains exactly one vertex in $X$. In other words,
there is exactly one $x\in X$ satisfying $x\in e$. Thus, the sum
$\sum_{\substack{x\in X;\\x\in e}}f\left( \overrightarrow{e}\right) $ has
exactly one addend. Hence, this sum simplifies as follows: $\sum
_{\substack{x\in X;\\x\in e}}f\left( \overrightarrow{e}\right) =f\left(
\overrightarrow{e}\right) $. This proves (\ref{pf.prop.hall.lem1.e.2}).}.
Hence, (\ref{pf.prop.hall.lem1.e.1}) becomes%
\begin{align}
\sum_{\substack{a\in A\text{ is an arc}\\\text{with source }s}}f\left(
a\right) & =\sum_{e\in E}\underbrace{\sum_{\substack{x\in X;\\x\in
e}}f\left( \overrightarrow{e}\right) }_{\substack{=f\left(
\overrightarrow{e}\right) \\\text{(by (\ref{pf.prop.hall.lem1.e.2}))}}%
}=\sum_{e\in E}f\left( \overrightarrow{e}\right) \nonumber\\
& =\sum_{\substack{e\in E;\\f\left( \overrightarrow{e}\right)
=0}}\underbrace{f\left( \overrightarrow{e}\right) }_{=0}+\sum
_{\substack{e\in E;\\f\left( \overrightarrow{e}\right) =1}%
}\underbrace{f\left( \overrightarrow{e}\right) }_{=1}\nonumber\\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because for any edge }e\in E\text{, we have}\\
\text{either }f\left( \overrightarrow{e}\right) =0\text{ or }f\left(
\overrightarrow{e}\right) =1\text{ (but not both)}%
\end{array}
\right) \nonumber\\
& =\underbrace{\sum_{\substack{e\in E;\\f\left( \overrightarrow{e}\right)
=0}}0}_{=0}+\sum_{\substack{e\in E;\\f\left( \overrightarrow{e}\right)
=1}}1=\sum_{\substack{e\in E;\\f\left( \overrightarrow{e}\right)
=1}}1\nonumber\\
& =\left\vert \underbrace{\left\{ e\in E\ \mid\ f\left( \overrightarrow{e}%
\right) =1\right\} }_{=M}\right\vert \cdot1=\left\vert M\right\vert
\cdot1=\left\vert M\right\vert . \label{pf.prop.hall.lem1.e.4}%
\end{align}
On the other hand, Observation 9 shows that there are no arcs $a\in A$ having
target $s$. Hence,
\begin{equation}
\sum_{\substack{a\in A\text{ is an arc}\\\text{with target }s}}f\left(
a\right) =\left( \text{empty sum}\right) =0. \label{pf.prop.hall.lem1.e.5}%
\end{equation}
But the definition of $\left\vert f\right\vert $ yields%
\begin{align*}
\left\vert f\right\vert & =\underbrace{f^{+}\left( s\right) }%
_{\substack{=\sum_{\substack{a\in A\text{ is an arc}\\\text{with source }%
s}}f\left( a\right) \\\text{(by the definition of }f^{+}\left( s\right)
\text{)}}}-\underbrace{f^{-}\left( s\right) }_{\substack{=\sum
_{\substack{a\in A\text{ is an arc}\\\text{with target }s}}f\left( a\right)
\\\text{(by the definition of }f^{-}\left( s\right) \text{)}}}\\
& =\underbrace{\sum_{\substack{a\in A\text{ is an arc}\\\text{with source }%
s}}f\left( a\right) }_{\substack{=\left\vert M\right\vert \\\text{(by
(\ref{pf.prop.hall.lem1.e.4}))}}}-\underbrace{\sum_{\substack{a\in A\text{ is
an arc}\\\text{with target }s}}f\left( a\right) }_{\substack{=0\\\text{(by
(\ref{pf.prop.hall.lem1.e.5}))}}}\\
& =\left\vert M\right\vert -0=\left\vert M\right\vert .
\end{align*}
In other words, $\left\vert M\right\vert =\left\vert f\right\vert $. This
proves Proposition \ref{prop.hall.lem1} \textbf{(e)}.
\end{proof}
As already mentioned, we omit the proof of the rest of Proposition
\ref{prop.hall.lem1}; it is an easy exercise on bookkeeping and understanding
the definitions of flows and matchings.
Proposition \ref{prop.hall.lem1} allows us to make the following definition:
\begin{definition}
We define a map%
\begin{align*}
\Phi:\left\{ \text{integer flows on }N\right\} & \rightarrow\left\{
\text{matchings in }G\right\} ,\\
f & \mapsto\left\{ e\in E\ \mid\ f\left( \overrightarrow{e}\right)
=1\right\} .
\end{align*}
This map is well-defined, because Proposition \ref{prop.hall.lem1}
\textbf{(d)} shows that if $f$ is an integer flow on $N$, then $\left\{ e\in
E\ \mid\ f\left( \overrightarrow{e}\right) =1\right\} $ is a matching in
$G$.
\end{definition}
We aim to show that this map $\Phi$ is a bijection. In order to do so, we will
construct its inverse, which of course will be a map transforming each
matching in $G$ into an integer flow on $N$. This requires the following
lemma:\footnote{We are again using the Iverson bracket notation.}
\begin{lemma}
\label{lem.hall.lem2}Let $M$ be any matching in $G$. Define a map
$f:A\rightarrow\mathbb{Q}_{+}$ by setting%
\begin{align*}
f\left( a\right) & =%
\begin{cases}
\left[ \text{there is an }e\in M\text{ such that }a=\overrightarrow{e}%
\right] , & \text{if }a\in A_{G};\\
\left[ x\text{ is matched in }M\right] , & \text{if }a=\left( s,x\right)
\text{ for some }x\in X;\\
\left[ y\text{ is matched in }M\right] , & \text{if }a=\left( y,t\right)
\text{ for some }y\in Y
\end{cases}
\\
& \ \ \ \ \ \ \ \ \ \ \text{for each }a\in A.
\end{align*}
Then, $f$ is an integer flow on $N$.
\end{lemma}
Again, the proof of Lemma \ref{lem.hall.lem2} is easy (just check that the
capacity and conservation constraints are satisfied).
Lemma \ref{lem.hall.lem2} allows us to define the following:
\begin{definition}
We define a map
\[
\Psi:\left\{ \text{matchings in }G\right\} \rightarrow\left\{ \text{integer
flows on }N\right\}
\]
by the requirement that $\Psi$ map any matching $M$ in $G$ to the integer flow
$f$ constructed in Lemma \ref{lem.hall.lem2}.
\end{definition}
\begin{proposition}
\label{prop.hall.inverse}\textbf{(a)} The maps $\Phi$ and $\Psi$ are mutually
inverse bijections between $\left\{ \text{integer flows on }N\right\} $ and
$\left\{ \text{matchings in }G\right\} $.
\textbf{(b)} For any integer flow $f$ on $N$, we have $\left\vert \Phi\left(
f\right) \right\vert =\left\vert f\right\vert $.
\end{proposition}
We leave the proof of Proposition \ref{prop.hall.inverse} to the reader again.
(It is fairly simple: Part \textbf{(b)} follows from Proposition
\ref{prop.hall.lem1} \textbf{(e)}. Part \textbf{(a)} requires proving that
$\Phi\circ\Psi=\operatorname*{id}$ and $\Psi\circ\Phi=\operatorname*{id}$. The
proof of $\Phi\circ\Psi=\operatorname*{id}$ is obvious; the proof of
$\Psi\circ\Phi=\operatorname*{id}$ relies on the conservation constraints.)
We now see how to find a matching in $G$ of maximum size. Indeed, we can find
an integer flow on $N$ of maximum value (see Remark \ref{rmk.3balg} for how
this is done). Then, the bijection $\Phi$ transforms this integer flow into a
matching in $G$ of maximum size (because Proposition \ref{prop.hall.inverse}
\textbf{(b)} shows that the value of an integer flow equals the size of the
matching corresponding to this flow under the bijection $\Phi$). Hence, we
obtain a matching in $G$ of maximum size.
We are also close to proving Theorem \ref{thm.hall} now. Before we do this,
let us prove a really simple lemma about matchings:
\begin{lemma}
\label{lem.hall.complete-mat}Let $\left( G;X,Y\right) $ be a bipartite
graph. Let $M$ be a matching in $G$.
\textbf{(a)} We have $\left\vert M\right\vert \leq\left\vert X\right\vert $.
\textbf{(b)} If $\left\vert M\right\vert \geq\left\vert X\right\vert $, then
the matching $M$ is $X$-complete.
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.hall.complete-mat} (sketched).]Recall that $\left(
G;X,Y\right) $ is a bipartite graph. Hence, each edge of $G$ contains exactly
one vertex in $X$ and exactly one vertex in $Y$. Thus, we can define a map
$\mathbf{x}:M\rightarrow X$ that sends each edge $e\in M$ to the unique vertex
in $X$ contained in $e$. Consider this map $\mathbf{x}$.
The map $\mathbf{x}$ is injective\footnote{\textit{Proof.} Let $m$ and $n$ be
two distinct elements of $M$. We want to prove that $\mathbf{x}\left(
m\right) \neq\mathbf{x}\left( n\right) $.
\par
Assume the contrary. Thus, $\mathbf{x}\left( m\right) =\mathbf{x}\left(
n\right) $. Define an $x\in X$ by $x=\mathbf{x}\left( m\right)
=\mathbf{x}\left( n\right) $. Now, $\mathbf{x}\left( m\right) $ is the
unique vertex in $X$ contained in $m$ (by the definition of $\mathbf{x}$). In
other words, $x$ is the unique vertex in $X$ contained in $m$ (since
$x=\mathbf{x}\left( m\right) $). Thus, $x$ is contained in $m$. In other
words, $x\in m$. Similarly, $x\in n$. The edges $m$ and $n$ are two distinct
edges in $M$, and have the endpoint $x$ in common (since $x\in m$ and $x\in
n$).
\par
But $M$ is a matching. Hence, no two distinct edges in $M$ have an endpoint in
common (by the definition of a matching). This contradicts that the edges $m$
and $n$ are two distinct edges in $M$ that have an endpoint in common (namely,
the vertex $x$). This contradiction shows that our assumption was wrong;
hence, $\mathbf{x}\left( m\right) \neq\mathbf{x}\left( n\right) $ is
proven.
\par
Now, forget that we fixed $m$ and $n$. We thus have shown that if $m$ and $n$
are two distinct elements of $M$, then $\mathbf{x}\left( m\right)
\neq\mathbf{x}\left( n\right) $. In other words, the map $\mathbf{x}$ is
injective.}. Hence, $\left\vert \mathbf{x}\left( M\right) \right\vert
=\left\vert M\right\vert $. Thus, $\left\vert M\right\vert =\left\vert
\mathbf{x}\left( M\right) \right\vert \leq\left\vert X\right\vert $ (since
$\mathbf{x}\left( M\right) \subseteq X$). This proves Lemma
\ref{lem.hall.complete-mat} \textbf{(a)}.
\textbf{(b)} Assume that $\left\vert M\right\vert \geq\left\vert X\right\vert
$. Combining this with $\left\vert M\right\vert \leq\left\vert X\right\vert $,
we obtain $\left\vert M\right\vert =\left\vert X\right\vert $.
Now, $\mathbf{x}\left( M\right) $ is a subset of $X$ that has the same size
as $X$ (because $\left\vert \mathbf{x}\left( M\right) \right\vert
=\left\vert M\right\vert =\left\vert X\right\vert $). But the only such subset
is $X$ itself (since $X$ is a finite set). Thus, $\mathbf{x}\left( M\right)
$ must be $X$. In other words, the map $\mathbf{x}$ is surjective. This shows
that the matching $M$ is $X$-complete\footnote{\textit{Proof.} Let $v\in X$ be
any vertex. Then, there exists some $m\in M$ such that $v=\mathbf{x}\left(
m\right) $ (since the map $\mathbf{x}$ is surjective). Consider this $m$. The
vertex $\mathbf{x}\left( m\right) $ is the unique vertex in $X$ contained in
$m$ (by the definition of $\mathbf{x}$). Hence, $\mathbf{x}\left( m\right) $
is contained in $m$. In other words, $\mathbf{x}\left( m\right) \in m$.
Hence, $v=\mathbf{x}\left( m\right) \in m$. In other words, $v$ is an
endpoint of $m$. Hence, there exists an edge $e\in M$ such that $v$ is an
endpoint of $e$ (namely, $e=m$). In other words, the vertex $v$ is matched in
$M$.
\par
Now, forget that we fixed $v$. We thus have shown that each vertex $v\in X$ is
matched in $M$. In other words, the matching $M$ is $X$-complete (by the
definition of \textquotedblleft$X$-complete\textquotedblright).}. This proves
Lemma \ref{lem.hall.complete-mat} \textbf{(b)}.
\end{proof}
Now, we can prove the following crucial lemma:
\begin{lemma}
\label{lem.hall.MU}Let $\left( G;X,Y\right) $ be a bipartite graph. Then,
there exist a matching $M$ in $G$ and a subset $U$ of $X$ satisfying
$\left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert
+\left\vert X\right\vert -\left\vert U\right\vert $.
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.hall.MU}.]Consider the network $N$. It clearly has
the property that $c\left( a\right) \in\mathbb{N}$ for each $a\in A$ (since
$c\left( a\right) =1$ for each $a\in A$). Hence, Lemma \ref{lem.3bat} shows
that there exist an integer flow $f:A\rightarrow\mathbb{Q}_{+}$ and a subset
$S$ of $V$ satisfying $s\in S$ and $t\notin S$ and $c\left( S,\overline
{S}\right) =\left\vert f\right\vert $. Consider these $f$ and $S$.
Let $U$ be the subset $X\cap S$ of $X$. Then, $N\left( U\right) \subseteq Y$
(by Proposition \ref{prop.bipartite.NXY}), so that $N\left( U\right) \cap
S\subseteq Y\cap S$ and thus $\left\vert N\left( U\right) \cap S\right\vert
\leq\left\vert Y\cap S\right\vert $. Also, $U=X\cap S\subseteq S$.
However, the set $N\left( U\right) $ is clearly the union of its two
disjoint subsets $N\left( U\right) \cap S$ and $N\left( U\right) \setminus
S$ (indeed, the former contains all the elements of $N\left( U\right) $ that
belong to $S$, whereas the latter contains all those that don't). Thus,%
\[
\left\vert N\left( U\right) \right\vert =\underbrace{\left\vert N\left(
U\right) \cap S\right\vert }_{\leq\left\vert Y\cap S\right\vert }+\left\vert
N\left( U\right) \setminus S\right\vert \leq\left\vert Y\cap S\right\vert
+\left\vert N\left( U\right) \setminus S\right\vert .
\]
Hence,%
\begin{equation}
\left\vert Y\cap S\right\vert +\left\vert N\left( U\right) \setminus
S\right\vert \geq\left\vert N\left( U\right) \right\vert .
\label{pf.thm.hall.hard.3}%
\end{equation}
But the set $X$ is the union of its two disjoint subsets $X\cap S$ and
$X\setminus S$. Hence,
\[
\left\vert X\right\vert =\left\vert \underbrace{X\cap S}_{=U}\right\vert
+\left\vert X\setminus S\right\vert =\left\vert U\right\vert +\left\vert
X\setminus S\right\vert .
\]
Thus,%
\begin{equation}
\left\vert X\setminus S\right\vert =\left\vert X\right\vert -\left\vert
U\right\vert . \label{pf.thm.hall.hard.4}%
\end{equation}
Lemma \ref{lem.hall.cPQ} (applied to $P=S$ and $Q=\overline{S}$) yields
$c\left( S,\overline{S}\right) =\left\vert \left[ S,\overline{S}\right]
\right\vert $. Thus,
\begin{equation}
\left\vert \left[ S,\overline{S}\right] \right\vert =c\left( S,\overline
{S}\right) =\left\vert f\right\vert . \label{pf.thm.hall.hard.5}%
\end{equation}
Let us now analyze the set $\left[ S,\overline{S}\right] $. This set
consists of all arcs $a\in A$ whose source lies in $S$ and whose target lies
in $\overline{S}$. Recall that the multidigraph $\left( V,A,\phi\right) $
has three kinds of arcs: the $G$-arcs, the $s$-arcs and the $t$-arcs. Some of
these arcs belong to $\left[ S,\overline{S}\right] $:
\begin{itemize}
\item For every vertex $x\in X\setminus S$, the $s$-arc $\left( s,x\right) $
belongs to $\left[ S,\overline{S}\right] $\ \ \ \ \footnote{\textit{Proof.}
Let $x\in X\setminus S$. Then, $x\in X\setminus S\subseteq X$, so that
$\left( s,x\right) \in A_{s}$ (by the definition of $A_{s}$). Thus, the arc
$\left( s,x\right) $ is an $s$-arc, and has source $s$ and target $x$.
Hence, the source of this arc lies in $S$ (since $s\in S$), but the target of
this arc lies in $\overline{S}$ (since $x\in\underbrace{X}_{\subseteq
V}\setminus S\subseteq V\setminus S=\overline{S}$). In other words, this arc
$\left( s,x\right) $ belongs to $\left[ S,\overline{S}\right] $. Qed.}. Of
course, these $s$-arcs $\left( s,x\right) $ are distinct (since their
targets $x$ are distinct). Thus, we have found a total of $\left\vert
X\setminus S\right\vert $ different $s$-arcs belonging to $\left[
S,\overline{S}\right] $ (one for each $x\in X\setminus S$).
\item For every vertex $y\in N\left( U\right) \setminus S$, there is at
least one $G$-arc with target $y$ that belongs to $\left[ S,\overline
{S}\right] $\ \ \ \ \footnote{\textit{Proof.} Let $y\in N\left( U\right)
\setminus S$. We must prove that there is at least one $G$-arc with target $y$
that belongs to $\left[ S,\overline{S}\right] $.
\par
We know that $y\in N\left( U\right) \setminus S\subseteq N\left( U\right)
$. In other words, $y$ has a neighbor in $U$ (by the definition of $N\left(
U\right) $). In other words, there exists some $x\in U$ such that $x$ is a
neighbor of $y$. Consider this $x$. Also, $y\in N\left( U\right) \subseteq
Y$.
\par
We know that $x$ is a neighbor of $y$. In other words, $\left\{ y,x\right\}
\in\psi\left( E\right) $ (by the definition of \textquotedblleft
neighbor\textquotedblright). In other words, $\left\{ y,x\right\}
=\psi\left( e\right) $ for some $e\in E$. Consider this $e$.
\par
Now, $e$ is an edge of $G$ (since $e\in E$) and has endpoints $y$ and $x$
(since $\psi\left( e\right) =\left\{ y,x\right\} $). Hence, the unique
endpoint of $e$ that lies in $X$ is $x$ (since $x\in U\subseteq X$), whereas
the unique endpoint of $e$ that lies in $Y$ is $y$ (since $y\in Y$). Hence,
the definition of $\overrightarrow{e}$ yields $\overrightarrow{e}=\left(
x,y,e\right) $.
\par
Now, $e\in E$ (since $e$ is an edge of $G$), and thus $\overrightarrow{e}\in
A_{G}$ (by the definition of $A_{G}$). Hence, $\left( x,y,e\right)
=\overrightarrow{e}\in A_{G}$. In other words, $\left( x,y,e\right) $ is a
$G$-arc. This $G$-arc $\left( x,y,e\right) $ has source $x$ and target $y$.
Thus, its source lies in $S$ (since $x\in U\subseteq S$) and its target lies
in $\overline{S}$ (since $y\in\underbrace{N\left( U\right) }_{\subseteq
V}\setminus S\subseteq V\setminus S=\overline{S}$). In other words, this
$G$-arc $\left( x,y,e\right) $ belongs to $\left[ S,\overline{S}\right] $.
Thus, there is at least one $G$-arc with target $y$ that belongs to $\left[
S,\overline{S}\right] $ (namely, the $G$-arc $\left( x,y,e\right) $).
Qed.}. If we pick one such $G$-arc for each vertex $y\in N\left( U\right)
\setminus S$, then we obtain a total of $\left\vert N\left( U\right)
\setminus S\right\vert $ distinct $G$-arcs belonging to $\left[
S,\overline{S}\right] $ (indeed, they are distinct because their targets $y$
are distinct).
\item For every vertex $y\in Y\cap S$, the $t$-arc $\left( y,t\right) $
belongs to $\left[ S,\overline{S}\right] $\ \ \ \ \footnote{\textit{Proof.}
Let $y\in Y\cap S$. Then, $y\in Y\cap S\subseteq Y$, so that $\left(
y,t\right) \in A_{t}$ (by the definition of $A_{t}$). Thus, $\left(
y,t\right) $ is a $t$-arc having source $y$ and target $t$. Hence, the source
of this arc lies in $S$ (since $y\in Y\cap S\subseteq S$), but the target of
this arc lies in $\overline{S}$ (since $t\in\overline{S}$ (because $t\notin
S$)). In other words, this arc $\left( y,t\right) $ belongs to $\left[
S,\overline{S}\right] $. Qed.}. Of course, these $t$-arcs $\left(
y,t\right) $ are distinct (since their sources $y$ are distinct). Thus, we
have found a total of $\left\vert Y\cap S\right\vert $ different $t$-arcs
belonging to $\left[ S,\overline{S}\right] $ (one for each $y\in Y\cap S$).
\end{itemize}
Now, recall that there is no overlap between the $G$-arcs, the $s$-arcs and
the $t$-arcs. Hence,%
\begin{align*}
\left\vert \left[ S,\overline{S}\right] \right\vert & =\underbrace{\left(
\text{the number of all }G\text{-arcs belonging to }\left[ S,\overline
{S}\right] \right) }_{\substack{\geq\left\vert N\left( U\right) \setminus
S\right\vert \\\text{(since we have found }\left\vert N\left( U\right)
\setminus S\right\vert \text{ different }G\text{-arcs belonging to }\left[
S,\overline{S}\right] \text{)}}}\\
& \ \ \ \ \ \ \ \ \ \ +\underbrace{\left( \text{the number of all
}s\text{-arcs belonging to }\left[ S,\overline{S}\right] \right)
}_{\substack{\geq\left\vert X\setminus S\right\vert \\\text{(since we have
found }\left\vert X\setminus S\right\vert \text{ different }s\text{-arcs
belonging to }\left[ S,\overline{S}\right] \text{)}}}\\
& \ \ \ \ \ \ \ \ \ \ +\underbrace{\left( \text{the number of all
}t\text{-arcs belonging to }\left[ S,\overline{S}\right] \right)
}_{\substack{\geq\left\vert Y\cap S\right\vert \\\text{(since we have found
}\left\vert Y\cap S\right\vert \text{ different }t\text{-arcs belonging to
}\left[ S,\overline{S}\right] \text{)}}}\\
& \geq\left\vert N\left( U\right) \setminus S\right\vert +\left\vert
X\setminus S\right\vert +\left\vert Y\cap S\right\vert \\
& =\underbrace{\left\vert Y\cap S\right\vert +\left\vert N\left( U\right)
\setminus S\right\vert }_{\substack{\geq\left\vert N\left( U\right)
\right\vert \\\text{(by (\ref{pf.thm.hall.hard.3}))}}}+\underbrace{\left\vert
X\setminus S\right\vert }_{\substack{=\left\vert X\right\vert -\left\vert
U\right\vert \\\text{(by (\ref{pf.thm.hall.hard.4}))}}}\\
& \geq\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert
-\left\vert U\right\vert .
\end{align*}
Hence, (\ref{pf.thm.hall.hard.5}) yields $\left\vert f\right\vert =\left\vert
\left[ S,\overline{S}\right] \right\vert \geq\left\vert N\left( U\right)
\right\vert +\left\vert X\right\vert -\left\vert U\right\vert $.
But let $M$ be the subset $\left\{ e\in E\ \mid\ f\left( \overrightarrow{e}%
\right) =1\right\} $ of $E$. Then, Proposition \ref{prop.hall.lem1}
\textbf{(d)} yields that the set $M=\left\{ e\in E\ \mid\ f\left(
\overrightarrow{e}\right) =1\right\} $ is a matching in $G$. Also,
Proposition \ref{prop.hall.lem1} \textbf{(e)} shows that
\[
\left\vert M\right\vert =\left\vert f\right\vert \geq\left\vert N\left(
U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert .
\]
We have thus found a matching $M$ in $G$ and a subset $U$ of $X$ satisfying
$\left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert
+\left\vert X\right\vert -\left\vert U\right\vert $. This proves Lemma
\ref{lem.hall.MU}.
\end{proof}
We can now easily prove Theorem \ref{thm.hall}:
\begin{proof}
[Proof of Theorem \ref{thm.hall} (sketched).]$\Longrightarrow:$ Assume that
$G$ has an $X$-complete matching. We must prove that each subset $U$ of $X$
satisfies $\left\vert N\left( U\right) \right\vert \geq\left\vert
U\right\vert $.
This is the so-called \textquotedblleft easy part\textquotedblright\ of
Theorem \ref{thm.hall}, and can be proven without any reference to flows and
cuts. Just fix an $X$-complete matching $M$ in $G$ (such a matching exists, by
assumption). Let $U$ be a subset of $X$. We must prove that $\left\vert
N\left( U\right) \right\vert \geq\left\vert U\right\vert $.
The matching $M$ is $X$-complete; thus, each vertex $x\in X$ has an
$M$-partner. Let $i:X\rightarrow Y$ be the map that sends each vertex $x\in X$
to its $M$-partner. Any two distinct elements of $X$ must have distinct
$M$-partners (because otherwise, the edges joining them to their common
$M$-partner would be two distinct edges in $M$ that have an endpoint in
common; but this is not allowed for a matching). In other words, the map $i$
is injective. Hence, every subset $Z$ of $X$ satisfies $\left\vert i\left(
Z\right) \right\vert =\left\vert Z\right\vert $. Applying this to $Z=U$, we
obtain $\left\vert i\left( U\right) \right\vert =\left\vert U\right\vert $.
But each $x\in U$ satisfies $i\left( x\right) \in N\left( U\right) $
(because the vertex $i\left( x\right) $ has a neighbor in $U$ (namely, the
vertex $x$)). In other words, $i\left( U\right) \subseteq N\left( U\right)
$. Hence, $\left\vert i\left( U\right) \right\vert \leq\left\vert N\left(
U\right) \right\vert $, so that $\left\vert N\left( U\right) \right\vert
\geq\left\vert i\left( U\right) \right\vert =\left\vert U\right\vert $.
Now, forget that we fixed $U$. We thus have shown that each subset $U$ of $X$
satisfies $\left\vert N\left( U\right) \right\vert \geq\left\vert
U\right\vert $. This proves the $\Longrightarrow$ direction of Theorem
\ref{thm.hall}.
$\Longleftarrow:$ Assume that
\begin{equation}
\text{each subset }U\text{ of }X\text{ satisfies }\left\vert N\left(
U\right) \right\vert \geq\left\vert U\right\vert .
\label{pf.thm.hall.hard.ass}%
\end{equation}
We must prove that $G$ has an $X$-complete matching.
Lemma \ref{lem.hall.MU} shows that there exist a matching $M$ in $G$ and a
subset $U$ of $X$ satisfying $\left\vert M\right\vert \geq\left\vert N\left(
U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert $.
Consider these $M$ and $U$. Then,%
\[
\left\vert M\right\vert \geq\underbrace{\left\vert N\left( U\right)
\right\vert }_{\substack{\geq\left\vert U\right\vert \\\text{(by
(\ref{pf.thm.hall.hard.ass}))}}}+\left\vert X\right\vert -\left\vert
U\right\vert \geq\left\vert U\right\vert +\left\vert X\right\vert -\left\vert
U\right\vert =\left\vert X\right\vert .
\]
Hence, Lemma \ref{lem.hall.complete-mat} \textbf{(b)} yields that the matching
$M$ is $X$-complete. Hence, $G$ has an $X$-complete matching (namely, $M$).
This proves the $\Longleftarrow$ direction of Theorem \ref{thm.hall}. Thus,
the proof of Theorem \ref{thm.hall} is complete.
\end{proof}
\subsection{K\"{o}nig's vertex cover theorem}
Lemma \ref{lem.hall.MU} puts us at a vantage point to prove not just Hall's
marriage theorem, but also its close relative, \textit{K\"{o}nig's vertex
cover theorem}. Before we state the latter theorem, we need to define the
concept of a vertex cover:
\begin{definition}
Let $G=\left( W,E,\psi\right) $ be a multigraph. Then, a \textit{vertex
cover} of $G$ means a subset $C$ of $W$ such that each edge $e\in E$ contains
at least one vertex in $C$.
\end{definition}
For example, if $G=\left( W,E,\psi\right) $ is the simple graph%
\begin{equation}%
%TCIMACRO{\TeXButton{a triangle}{\xymatrix{
%& 1 \are[dl] \are[dr] \\
%2 \are[rr] & & 3
%}} }%
%BeginExpansion
\xymatrix{
& 1 \are[dl] \are[dr] \\
2 \are[rr] & & 3
}
%EndExpansion
\label{eq.hall.vertexcover.ex1}%
\end{equation}
(regarded as a multigraph), then every $2$-element subset of $W$ is a vertex
cover (but no smaller subset of $W$ is). Clearly, any multigraph $G=\left(
W,E,\psi\right) $ has at least one vertex cover (because the whole set $W$ is
always a vertex cover). A
\href{https://en.wikipedia.org/wiki/Vertex_cover}{classical problem in
computer science} is to find a vertex cover of a given multigraph whose size
is minimum.
Now, \textit{K\"{o}nig's theorem on vertex covers} states the following:
\begin{theorem}
\label{thm.hall.koenig}Let $\left( G;X,Y\right) $ be a bipartite graph.
Then, the maximum size of a matching in $G$ equals the minimum size of a
vertex cover of $G$.
\end{theorem}
Notice that the claim of Theorem \ref{thm.hall.koenig} isn't true for
arbitrary graphs $G$; for example, if $G$ is the simple graph in
(\ref{eq.hall.vertexcover.ex1}), then the maximum size of a matching in $G$ is
$1$, but the minimum size of a vertex cover of $G$ is $2$. Nevertheless, the
claim is true when $G$ is part of a bipartite graph $\left( G;X,Y\right) $.
What is true for arbitrary graphs $G$ is the following inequality:
\begin{proposition}
\label{prop.hall.koenig.<=}Let $G$ be a multigraph. Then, the maximum size of
a matching in $G$ is $\leq$ to the minimum size of a vertex cover of $G$.
\end{proposition}
\begin{proof}
[Proof of Proposition \ref{prop.hall.koenig.<=}.]Let $m$ be the maximum size
of a matching in $G$. Let $c$ be the minimum size of a vertex cover of $G$. We
must prove that $m\leq c$.
There exists a matching $M$ in $G$ such that $\left\vert M\right\vert =m$
(since $m$ is the size of a matching in $G$). Consider this $M$.
There exists a vertex cover $C$ of $G$ such that $\left\vert C\right\vert =c$
(since $c$ is the size of a vertex cover of $G$). Consider this $C$.
Write the multigraph $G$ in the form $G=\left( W,E,\psi\right) $. Recall
that $C$ is a vertex cover of $G$. In other words, $C$ is a subset of $W$ such
that each edge $e\in E$ contains at least one vertex in $C$ (by the definition
of a \textquotedblleft vertex cover\textquotedblright).
Each edge $e\in E$ contains at least one vertex in $C$. In other words, for
each edge $e\in E$, there is at least one vertex $v\in C$ such that $v\in e$.
In other words, for each edge $e\in E$, we have%
\begin{equation}
\left( \text{the number of }v\in C\text{ such that }v\in e\right) \geq1.
\label{pf.prop.hall.koenig.<=.>=}%
\end{equation}
On the other hand, $M$ is a matching in $G$. In other words, $M$ is a subset
of $E$ such that no two distinct edges in $M$ have an endpoint in common (by
the definition of a \textquotedblleft matching\textquotedblright). No two
distinct edges in $M$ have an endpoint in common. In other words, no vertex of
$G$ is contained in more than one edge in $M$. In other words, each vertex of
$G$ is contained in at most one edge in $M$. In other words, for each vertex
$v$ of $G$, there is at most one edge $e\in M$ such that $v\in e$. In other
words, for each vertex $v$ of $G$, we have%
\begin{equation}
\left( \text{the number of edges }e\in M\text{ such that }v\in e\right)
\leq1. \label{pf.prop.hall.koenig.<=.<=}%
\end{equation}
Now,
\begin{align*}
& \left( \text{the number of pairs }\left( v,e\right) \in C\times M\text{
such that }v\in e\right) \\
& =\sum_{v\in C}\underbrace{\left( \text{the number of edges }e\in M\text{
such that }v\in e\right) }_{\substack{\leq1\\\text{(by
(\ref{pf.prop.hall.koenig.<=.<=}))}}}\leq\sum_{v\in C}1\\
& =\left\vert C\right\vert \cdot1=\left\vert C\right\vert =c.
\end{align*}
Thus,%
\begin{align*}
c & \geq\left( \text{the number of pairs }\left( v,e\right) \in C\times
M\text{ such that }v\in e\right) \\
& =\sum_{e\in M}\underbrace{\left( \text{the number of }v\in C\text{ such
that }v\in e\right) }_{\substack{\geq1\\\text{(by
(\ref{pf.prop.hall.koenig.<=.>=}))}}}\geq\sum_{e\in M}1\\
& =\left\vert M\right\vert \cdot1=\left\vert M\right\vert =m.
\end{align*}
In other words, $m\leq c$. This completes our proof of Proposition
\ref{prop.hall.koenig.<=}.
\end{proof}
\begin{proof}
[Proof of Theorem \ref{thm.hall.koenig} (sketched).]Let $m$ be the maximum
size of a matching in $G$. Let $c$ be the minimum size of a vertex cover of
$G$. We must prove that $m=c$.
Proposition \ref{prop.hall.koenig.<=} yields $m\leq c$.
Write the multigraph $G$ in the form $G=\left( W,E,\psi\right) $.
Lemma \ref{lem.hall.MU} shows that there exist a matching $M$ in $G$ and a
subset $U$ of $X$ satisfying $\left\vert M\right\vert \geq\left\vert N\left(
U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert $.
Consider these $M$ and $U$.
The size $\left\vert M\right\vert $ of the matching $M$ is clearly $\leq$ to
the maximum size of a matching in $G$. In other words, $\left\vert
M\right\vert \leq m$ (since $m$ is the maximum size of a matching in $G$).
Thus,%
\begin{equation}
m\geq\left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert
+\left\vert X\right\vert -\left\vert U\right\vert .
\label{pf.thm.hall.koenig.m>=}%
\end{equation}
On the other hand, let $C$ be the subset $\left( X\setminus U\right) \cup
N\left( U\right) $ of $W$. Then, we have the following:
\begin{statement}
\textit{Observation 1:} The set $C$ is a vertex cover of $G$.
\end{statement}
[\textit{Proof of Observation 1:} Let $e\in E$ be any edge. We shall show that
$e$ contains at least one vertex in $C$.
Indeed, assume the contrary. Thus, $e$ contains no vertex in $C$.
Each edge of $G$ contains exactly one vertex in $X$ and exactly one vertex in
$Y$ (since $\left( G;X,Y\right) $ is a bipartite graph). Thus, in
particular, each edge of $G$ contains exactly one vertex in $X$. Applying this
to the edge $e$, we conclude that the edge $e$ contains exactly one vertex in
$X$. Let $x$ be this vertex. Thus, $x\in X$, and the edge $e$ contains the
vertex $x$. If we had $x\in C$, then $e$ would contain a vertex in $C$
(namely, the vertex $x$), which would contradict the fact that $e$ contains no
vertex in $C$. Hence, we cannot have $x\in C$. Thus, we have $x\notin C$.
Hence, $x\in X\setminus C$.
But $C=\left( X\setminus U\right) \cup N\left( U\right) \supseteq
X\setminus U$, so that $X\setminus\underbrace{C}_{\supseteq X\setminus
U}\subseteq X\setminus\left( X\setminus U\right) =U$ (since $U\subseteq X$).
Hence, $x\in X\setminus C\subseteq U$.
Now, let $y$ be the endpoint of the edge $e$ distinct from $x$. (This is
well-defined, since we already know that $e$ contains $x$.) Then, $x$ and $y$
are the two endpoints of the edge $e$. Hence, $\psi\left( e\right) =\left\{
x,y\right\} $. Thus, $\left\{ y,x\right\} =\left\{ x,y\right\}
=\psi\left( \underbrace{e}_{\in E}\right) \in\psi\left( E\right) $; in
other words, $x$ is a neighbor of $y$. Hence, the vertex $y$ has a neighbor in
$U$ (namely, the neighbor $x$). In other words, $y\in N\left( U\right) $ (by
the definition of $N\left( U\right) $). Hence, $y\in N\left( U\right)
\subseteq\left( X\setminus U\right) \cup N\left( U\right) =C$. In other
words, $y$ is a vertex in $C$. Thus, the edge $e$ contains at least one vertex
in $C$ (namely, the vertex $y$), because $e$ contains $y$. This contradicts
the fact that $e$ contains no vertex in $C$.
This contradiction proves that our assumption was wrong. Hence, we have shown
that $e$ contains at least one vertex in $C$.
Now, forget that we fixed $e$. We thus have proven that each edge $e\in E$
contains at least one vertex in $C$. In other words, $C$ is a vertex cover of
$G$ (by the definition of \textquotedblleft vertex cover\textquotedblright).
This proves Observation 1.]
Now, $C=\left( X\setminus U\right) \cup N\left( U\right) $, so that
\begin{align*}
\left\vert C\right\vert & =\left\vert \left( X\setminus U\right) \cup
N\left( U\right) \right\vert \leq\underbrace{\left\vert X\setminus
U\right\vert }_{\substack{=\left\vert X\right\vert -\left\vert U\right\vert
\\\text{(since }U\subseteq X\text{)}}}+\left\vert N\left( U\right)
\right\vert \\
& \ \ \ \ \ \ \ \ \ \ \left( \text{this is in fact an equality, but we don't
need this}\right) \\
& =\left\vert X\right\vert -\left\vert U\right\vert +\left\vert N\left(
U\right) \right\vert =\left\vert N\left( U\right) \right\vert +\left\vert
X\right\vert -\left\vert U\right\vert \leq m\ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{pf.thm.hall.koenig.m>=})}\right) .
\end{align*}
But the set $C$ is a vertex cover of $G$ (by Observation 1). Hence, its size
$\left\vert C\right\vert $ is $\geq$ to the minimum size of a vertex cover of
$G$. In other words, $\left\vert C\right\vert \geq c$ (since $c$ is the
minimum size of a vertex cover of $G$). Thus, $c\leq\left\vert C\right\vert
\leq m$. Combining this with $m\leq c$, we obtain $m=c$. This completes the
proof of Theorem \ref{thm.hall.koenig}.
\end{proof}
\begin{thebibliography}{999999999} %
\bibitem[ForFul62]{ForFul62}L. R. Ford (Jr.) and D. R. Fulkerson,
\textit{Flows in Networks}, Princeton University Press 1962.\newline A
preprint is freely available at
\url{https://www.rand.org/content/dam/rand/pubs/reports/2007/R375.pdf} .
\bibitem[Goeman17]{Goeman17}Michel X. Goemans, \textit{18.453 Combinatorial
Optimization}, course at MIT, Spring 2017.\newline\url{http://math.mit.edu/~goemans/18453S17/18453.html}
\bibitem[Grinbe17b]{lec16}Darij Grinberg, \textit{UMN, Spring 2017, Math 5707:
Lecture 16 (flows and cuts in networks)}, \newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/t/17s/5707lec16.pdf} .
\bibitem[LeLeMe17]{LeLeMe17}Eric Lehman, F. Thomson Leighton, Albert R. Meyer,
\textit{Mathematics for Computer Science}, version 15 November 2017.\newline\url{https://courses.csail.mit.edu/6.042/fall17/mcs.pdf}
\bibitem[Martin17]{Martin17}Jeremy L. Martin, \textit{Lecture Notes on
Algebraic Combinatorics}, 8 June 2017.\newline\url{http://people.ku.edu/~jlmartin/LectureNotes.pdf}
\bibitem[Schrij12]{Schrij12}%
\href{https://www.math.uni-bielefeld.de/documenta/vol-ismp/33_schrijver-alexander-tmf.pdf}{Alexander
Schrijver, \textit{On the History of the Transportation and Maximum Flow
Problems}, Documenta Mathematica, Extra Volume ISMP (2012), pp. 169--180.}
\bibitem[Schrij17]{Schrij17}Alexander (Lex) Schrijver, \textit{A Course in
Combinatorial Optimization}, 23 March 2017.\newline\url{https://homepages.cwi.nl/~lex/files/dict.pdf}
\bibitem[Thalwi08]{Thalwi08}Timon Thalwitzer, \textit{Max-Flow Min-Cut},
diploma thesis at Universit\"{a}t Wien.\newline\url{http://www.mat.univie.ac.at/~kratt/theses/thalwitz.pdf}
\bibitem[Zwick95]{Zwick95}%
\href{https://doi.org/10.1016/0304-3975(95)00022-O}{Uri Zwick, \textit{The
smallest networks on which the Ford-Fulkerson maximum flow procedure may fail
to terminate}, Theoretical Computer Science \textbf{148}, Issue 1, 21 August
1995, pp. 165--170}.
\end{thebibliography}
\end{document}