Matchings, Covers, Menger and Network Flows

Let $G=(V,E)$ be a finite simple graph. A matching is a set $M\subseteq E$ such that no two distinct edges of $M$ have a common endpoint. A vertex is $M$-saturated when it is an endpoint of an edge of $M$, and $M$-exposed otherwise. The matching is perfect when every vertex is $M$-saturated.

A matching is maximal when no strictly larger matching contains it, and is maximum when it has greatest cardinality among all matchings of $G$. The matching number is $\nu(G):=\max\{\lvert M\rvert:M\text{ is a matching of }G\}.$ The maximum exists because $E$ is finite and the empty set is a matching.

• A maximal matching need not be maximum; the companion counterexample makes the distinction concrete.

Every maximum matching is maximal: a strict matching extension has strictly larger cardinality. The converse is not a definition and is false in general; maximal only rules out adding edges while preserving the ones already chosen.

For a finite simple graph $G=(V,E)$, a vertex cover is a set $C\subseteq V$ such that every edge has an endpoint in $C$; its least possible size is $\tau(G):=\min\{\lvert C\rvert:C\text{ is a vertex cover of }G\}.$ An edge cover is a set $F\subseteq E$ such that every vertex is incident with an edge of $F$; if $G$ has no isolated vertices, its least possible size is $\rho(G):=\min\{\lvert F\rvert:F\text{ is an edge cover of }G\}.$ Both extrema exist whenever their displayed families are nonempty, since $V$ and $E$ are finite. An isolated vertex prevents every edge cover.

Let $M$ be a matching of $G$. A path is $M$-alternating if consecutive edges alternately lie outside and inside $M$. It is $M$-augmenting if it is $M$-alternating, its first and last edges lie outside $M$, and its two endpoints are $M$-exposed. Thus an augmenting path has odd length, including the possible one-edge path between two exposed vertices.

If $P$ is an $M$-augmenting path in a finite graph, then $M':=M\mathbin{\triangle}E(P)$ is a matching and $|M'|=|M|+1$.

• The use of symmetric difference is literal: it deletes the old matching edges on $P$ and inserts the new ones, with no choice of any further edges.

For matchings $M,N$ of a finite graph $G$, every nontrivial connected component of the spanning subgraph with edge set $M\triangle N$ is an alternating path or an even alternating cycle. The components are edge-disjoint.

A matching $M$ in a finite graph is maximum if and only if no $M$-augmenting path exists.

• Finiteness is used only to ensure that a nonmaximum matching has a larger matching and to make the component count finite.

Let $G$ be a finite bipartite graph with specified parts $X$ and $Y$. For $S\subseteq X$, its neighbourhood in $Y$ is $N(S):=\{y\in Y:xy\in E(G)\text{ for some }x\in S\}.$ The pair $(X,Y)$ satisfies Hall's condition (on $X$) if $|N(S)|\ge |S|$ for every $S\subseteq X$.

For any indexed family $(A_x)_{x\in X}$, write $U:=\bigcup_{x\in X}A_x$. A system of distinct representatives (SDR) is an injection $r:X\to U$ such that $r(x)\in A_x$ for every $x\in X$.

When $X$ and $U$ are finite, the incidence graph of the family is the finite bipartite graph with the disjoint tagged parts $X_{\mathrm L}:=\{(x,\mathrm L):x\in X\},\qquad U_{\mathrm R}:=\{(u,\mathrm R):u\in U\}.$ and an edge $(x,\mathrm L)(u,\mathrm R)$ exactly when $u\in A_x$. For $S\subseteq X$, its left tagged copy has neighbourhood $N(S_{\mathrm L})=\{(u,\mathrm R):u\in\bigcup_{x\in S}A_x\}.$

Let $(X,Y)$ satisfy Hall's condition. If $|X|\ge2$, then exactly one of the following usable reductions holds.

1. Strict case: if $|N(S)|>|S|$ for every nonempty proper $S\subset X$, then for every edge $xy$ the graph obtained by deleting $x$ and $y$ satisfies Hall's condition on $X\setminus\{x\}$.
2. Tight case: if some nonempty proper $S\subset X$ has $|N(S)|=|S|$, then both the subgraph on $S\cup N(S)$ and the subgraph on $(X\setminus S)\cup(Y\setminus N(S))$ satisfy Hall's condition on their respective left parts.

• The two alternatives are exhaustive by whether a nonempty proper left subset is tight; the one-vertex case is kept in Hall's theorem rather than forced into this reduction.

For a finite bipartite graph with parts $(X,Y)$, there is a matching saturating $X$ if and only if $|N(S)|\ge |S|$ for every $S\subseteq X$.

• This is the finite theorem only. No infinite-family or choice-principle claim is being made here.

Let $(A_x)_{x\in X}$ have finite index set $X$ and finite union $U:=\bigcup_{x\in X}A_x$. It has an SDR if and only if $\left|\bigcup_{x\in S}A_x\right|\ge |S|\qquad(S\subseteq X).$

Let $(X,Y)$ be a finite bipartite graph and put $d:=\max_{S\subseteq X}\bigl(|S|-|N(S)|\bigr).$ Then the greatest number of vertices of $X$ saturable by a matching is $|X|-d$.

Let $G$ have bipartition $(X,Y)$ and let $M$ be a maximum matching. From every $M$-exposed vertex of $X$, follow alternating paths that begin with a nonmatching edge. Let $Z_X\subseteq X$ and $Z_Y\subseteq Y$ be the reachable vertices in the two parts. Then $C:=(X\setminus Z_X)\cup Z_Y$ is a vertex cover and $|C|=|M|$.

• The direction of alternation is essential: left-to-right steps are nonmatching edges and right-to-left steps are matching edges.

For every finite bipartite graph $G$, its matching number and vertex-cover number agree: $\nu(G)=\tau(G)$.

If a finite graph $G=(V,E)$ has no isolated vertex, then its matching and edge-cover numbers satisfy $\nu(G)+\rho(G)=|V|$.

• The no-isolated-vertex hypothesis is load-bearing: an isolated vertex has no incident edge, so no edge cover exists.

A finite integral $s$-$t$ network is a tuple $\mathcal N=(V,A,\operatorname{tail},\operatorname{head},s,t,c)$ where $V$ and the labelled arc set $A$ are finite, $s,t\in V$ are distinct, $\operatorname{tail},\operatorname{head}:A\longrightarrow V,$ every arc $a\in A$ has $\operatorname{tail}(a)\ne\operatorname{head}(a)$, $c:A\to\mathbb N$, no arc enters $s$, and no arc leaves $t$. Parallel and antiparallel arcs are allowed because distinct elements of $A$ remain distinct.

A feasible integral flow is $f:A\to\mathbb N$ with $0\le f(a)\le c(a)$ and $\sum_{\operatorname{tail}(a)=v}f(a)=\sum_{\operatorname{head}(a)=v}f(a)\quad(v\in V\setminus\{s,t\}).$ Its value is $|f|:=\sum_{\operatorname{tail}(a)=s}f(a)$. An $s$-$t$ cut is a set $S\subseteq V$ with $s\in S$, $t\notin S$; its capacity is $c(S):=\sum_{\operatorname{tail}(a)\in S,\operatorname{head}(a)\notin S}c(a)$.

The residual network of $f$ has the labelled copies $R_f=\{(a,+):f(a)<c(a)\}\cup\{(a,-):f(a)>0\}.$ On these copies, put $\begin{aligned}\operatorname{tail}_f(a,+)&=\operatorname{tail}(a),&\operatorname{head}_f(a,+)&=\operatorname{head}(a),&r_f(a,+)&=c(a)-f(a),\\\operatorname{tail}_f(a,-)&=\operatorname{head}(a),&\operatorname{head}_f(a,-)&=\operatorname{tail}(a),&r_f(a,-)&=f(a).\end{aligned}$ For $x,y\in V$, an $x$-$y$ residual path is a sequence $\rho_1,\ldots,\rho_k$ of members of $R_f$, with $k\ge1$, for which $\operatorname{tail}_f(\rho_1)=x,\qquad \operatorname{head}_f(\rho_k)=y,\qquad \operatorname{head}_f(\rho_i)=\operatorname{tail}_f(\rho_{i+1})\quad(1\le i<k),$ and the vertex list $x,\operatorname{head}_f(\rho_1),\ldots,\operatorname{head}_f(\rho_k)=y$ has no repetitions. Thus the path records the selected labelled copies, so $(a,-)$ never coincides with a forward copy of an antiparallel original arc.

• Capacities and flows are natural numbers here. No rational, real, or infinite-capacity termination assertion is part of this definition.

For a feasible flow $f$ and every $s$-$t$ cut $S$, $|f|+\sum_{\operatorname{tail}(a)\notin S,\operatorname{head}(a)\in S}f(a)=\sum_{\operatorname{tail}(a)\in S,\operatorname{head}(a)\notin S}f(a)\le c(S).$ In particular $|f|\le c(S)$.

If $P$ is an $s$-$t$ residual path for a feasible integral flow $f$, and $\delta$ is the least residual capacity of a copy on $P$, then adding $\delta$ on each original arc used as $(a,+)$ and subtracting $\delta$ on each original arc used as $(a,-)$ gives a feasible integral flow $f'$ with $|f'|=|f|+\delta$.

• The sign is attached to an arc label, not merely to its endpoints. This is what keeps a reverse copy separate from an antiparallel original arc.

If no residual $s$-$t$ path exists for a feasible flow $f$, let $S$ be the vertices reachable from $s$ in its residual network. Then $S$ is an $s$-$t$ cut and $c(S)=|f|$.

In a finite integral $s$-$t$ network, begin with the zero flow and repeatedly augment along any residual $s$-$t$ path by its integral bottleneck. This process terminates. Its final integral flow $f^*$ is maximum, and $|f^*|=\min\{c(S):S\text{ is an }s\text{-}t\text{ cut}\}.$

• Integer bottlenecks are the termination mechanism. This theorem makes no assertion about arbitrary real capacities.

Every feasible integral flow is a finite sum of unit $s$-$t$ path flows and unit directed cycle flows. Here a labelled directed cycle flow also permits a two-arc antiparallel circuit, so that it records a circulation even when the underlying simple-digraph convention excludes two-cycles. If every capacity is at most one, the source-sink paths in such a decomposition are arc-disjoint.

For a finite bipartite graph with parts $(X,Y)$, give the arcs $s\to x$, each graph edge $x\to y$, and $y\to t$ unit capacity. Integral flow paths correspond to matching edges $xy$; a vertex cover $C_X\cup C_Y$ gives the cut $\{s\}\cup(X\setminus C_X)\cup C_Y$ of the same size. Consequently the maximum-flow/minimum-cut equality agrees with the matching/cover equality, and a flow of value $|X|$ agrees with Hall's saturating matching criterion.

For the following definitions, a directed path occurrence in a finite labelled directed graph $(V,A,\operatorname{tail},\operatorname{head})$, where $V,A$ are finite and $\operatorname{tail},\operatorname{head}:A\to V$, is an alternating list $v_0,a_1,v_1,\ldots,a_\ell,v_\ell$ with $a_i\in A$, $\operatorname{tail}(a_i)=v_{i-1}$, and $\operatorname{head}(a_i)=v_i$ for every $i$, whose displayed vertices are distinct. An undirected path occurrence in a finite undirected multigraph (Multigraphs, loops and directed graphs as variants distinct from the default finite simple graph) is an alternating list $v_0,e_1,v_1,\ldots,e_\ell,v_\ell$ whose displayed vertices are distinct and whose displayed edge $e_i$ has endpoint set $\{v_{i-1},v_i\}$ for every $i$. Thus each path records its arc or edge labels, including when parallel labels have the same endpoints. An ordinary graph uses each edge $e\in E$ as its own label with endpoint set $e$, while an ordinary digraph uses each ordered-pair arc $(u,v)$ as its own label with $\operatorname{tail}(u,v)=u$ and $\operatorname{head}(u,v)=v$.

For distinct $s,t\in V$, a family of directed $s$-$t$ path occurrences is arc-disjoint if no arc label occurs in two paths; an arc separator is a set of arc labels whose deletion leaves no directed $s$-$t$ path occurrence. For an undirected multigraph, replace arc labels by edge labels to obtain edge-disjoint paths and edge separators. Deleting labels means removing exactly those labels while retaining the other incidence data.

An $s$-$t$ path family is internally vertex-disjoint if no vertex other than $s,t$ occurs in two paths. A vertex separator is a set $S\subseteq V\setminus\{s,t\}$ for which deleting $S$, together with every incident arc or edge label, leaves no $s$-$t$ path occurrence. The local vertex comparison is used only when the terminals are nonadjacent (or, in the directed case, when no arc label has tail $s$ and head $t$), so that such a separator can exist.

All graphs below are finite and the terminals $s,t$ are distinct.

1. In a directed graph, the maximum number of arc-disjoint directed $s$-$t$ paths equals the minimum size of an arc separator.
2. In an undirected graph, the maximum number of edge-disjoint $s$-$t$ paths equals the minimum size of an edge separator.
3. In a directed graph with no arc $s\to t$, the maximum number of internally vertex-disjoint directed $s$-$t$ paths equals the minimum size of a vertex separator.
4. In an undirected graph with nonadjacent $s,t$, the maximum number of internally vertex-disjoint $s$-$t$ paths equals the minimum size of a vertex separator.

• The undirected edge reduction cancels opposed flow before decomposition. This prevents two output paths from consuming the two orientations of one original undirected edge.

Let $k\ge1$ and let $G$ be a finite graph on at least $k+1$ vertices. Then $G$ is $k$-connected, meaning it is connected and $\kappa(G)\ge k$, if and only if every two distinct vertices of $G$ are joined by at least $k$ internally vertex-disjoint paths.