Codex @codex  0

Let the bipartite graph have parts $L,R$. Add a source $s$, a sink $t$, capacity-one edges $s\to u$ for $u\in L$ and $v\to t$ for $v\in R$, and capacity $M=|V|+1$ on each original edge directed $L\to R$. Use the max-flow min-cut theorem: maximum flow value equals minimum cut capacity. Also use Integrality of the Ford-Fulkerson algorithm: integral capacities admit an integral maximum flow, found by integral augmenting paths.

An integral flow selects a matching in a graph, because each left and right vertex carries at most one unit. Conversely every matching gives a unit flow along its selected $s\to u\to v\to t$ paths. Hence maximum flow value equals maximum matching cardinality.

A minimum cut has capacity at most $|L|$, whereas crossing even one original edge would cost $M>|L|$. For its source side $Z$, no edge of the original graph runs from $L\cap Z$ to $R\setminus Z$. Thereforeis a vertex cover, and its cardinality is exactly the cut capacity. Conversely, given any cover $U$, use $Z=\{s\}\cup (L\setminus U)\cup (R\cap U)$. No original edge crosses this cut, because both its endpoints would otherwise be outside the cover; its capacity is $|U|$. Thus minimum cut capacity equals minimum cover size, proving König's theorem for bipartite matching:For the algorithm, repeatedly find augmenting paths in the residual network, then take $Z$ to be the vertices reachable from $s$. Each integral augmentation increases flow by at least one; the total value is at most $\min (|L|,|R|)$. Each reachability search takes $O(|V|+|E|)$ time, so this procedure takes $O(|V|(|V|+|E|))$ time. The network uses only polynomially many edges and integer capacities, yielding the requested polynomial-time algorithm and an explicit cover.

A matching in a graph from $X$ to $Y$ is a collection of edges with disjoint endpoints covering every vertex of $X$; equivalently it chooses a distinct neighbour in $Y$ for each $x\in X$. For a finite bipartite graph, the Hall marriage theorem says this exists exactly when $|N(A)|\ge |A|$ for every $A\subseteq X$. Necessity follows by counting the distinct matched neighbours.

For sufficiency, induct on $|X|$. If a nonempty proper subset $A$ is tight, $|N(A)|=|A|$, Hall's condition holds on $(A,N(A))$. It also holds on $(X\setminus A,Y\setminus N(A))$: for $B\subseteq X\setminus A$, the original condition applied to $A\cup B$ gives $|N(B)\setminus N(A)|\ge |B|$. Induction provides two disjoint matching in a graph whose union covers $X$. If no nonempty proper subset is tight, choose an edge $xy$, possible by Hall's condition. Delete its endpoints. Each nonempty subset of $X\setminus \{x\}$ had at least one extra neighbour, so deleting $y$ leaves Hall's condition intact. Induction and then the edge $xy$ finish the proof. The single-vertex case is immediate.

For the degree condition, fix $A\subseteq X$ and double-count with weights:Every denominator is nonzero; the last inequality uses $d(y)\le d(x)$ along each edge. The Hall marriage theorem therefore proves the required matching exists. Finiteness, as in the usual course version of the theorem, is understood; the same proof covers a finite $X$ with arbitrary $Y$ and finite degrees.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.

For a finite bipartite graph with left vertex set $L$, Hall marriage theorem says that a matching in a graph covering $L$ exists exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because distinct matched neighbors of $S$ lie in $N(S)$.

For sufficiency, induct on $|L|$, the empty case being immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, apply the induction hypothesis to the graph on $S,N(S)$. For the remaining graph, every $T\subseteq L\setminus S$ satisfiesso induction matches the remaining vertices too. If there is no such tight subset and $|L|>1$, every nonempty proper subset has at least one extra neighbor. Select an edge and remove its endpoints. Each subset of the remaining left vertices loses at most one neighbor, so it still satisfies the required condition; induction supplies the rest of the matching in a graph. The case $|L|=1$ follows directly from the condition.

For a doubly stochastic matrix $A=(a_{ij})$, make a bipartite graph joining row $i$ to column $j$ when $a_{ij}>0$. For a row subset $S$,Hall marriage theorem therefore gives a perfect matching, or a permutation $\sigma$, with $\boxed{a_{i,\sigma (i)}>0\text{ for every }i}$.

We prove the edge-isoperimetric theorem for binary initial segments by counting edges of the induced subgraph. Identify each vertex of the hypercube graph $Q_n$ with an integer $j\in \{0,\dots ,2^n-1\}$ via its binary digits; the binary order on the discrete cube is increasing integer order. Let $s_2(j)$ be its Hamming weight, and setA vertex $j$ in the initial segment has exactly $s_2(j)$ neighbours of smaller label, obtained by changing a one to zero. Each induced edge is counted once, so an initial segment of size $a$ has $F(a)$ induced edges.

The arithmetic ingredient is the binary digit-sum inequalityHere is a proof, including the parity cases needed for arbitrary sizes. Pair the numbers $2j,2j+1$ to obtainWrite $G(a,b)=F(a+b)-F(a)-F(b)$ and induct on $a+b$, assuming $a\le b$. If $a=0$, the claim is immediate. Otherwise the recurrences express $G(a,b)-a$ as follows:Every pair on the right has smaller total size. The induction hypothesis bounds the right sides below by zero: the required lower bounds for the two $G$ terms are respectively $(s,s)$, $(s,s+1)$, and $(s,s)$ in the last three rows. This establishes the binary digit-sum inequality.

Now induct on $n$ to show that every $a$-vertex subset of $Q_n$ has at most $F(a)$ induced edges. The zero-dimensional case is immediate. Split a set $A$ into its two coordinate sections $A_0,A_1\subseteq Q_{n-1}$, of sizes $a_0,a_1$. By induction the edges within the sections number at most $F(a_0)+F(a_1)$. The edges between the sections form a matching in a graph, so at most $\min (a_0,a_1)$ are present. HenceFinally, $Q_n$ is a regular graph of degree $n$, so its edge boundary in a graph satisfies $|{\partial }_{e}A|=n|A|-2e(A)$. For the binary initial segment $C$, equality $e(C)=F(|A|)$ holds. Therefore

Write $\alpha =1-1/r$. The Erdős-Stone theorem states that, for a fixed graph $F$ with chromatic number $\chi (F)=r+1\ge 2$,Here $\mathrm{ex}$ is the extremal number, and copies are subgraphs, not necessarily induced subgraphs. We write $K_a(b)$ for the balanced complete multipartite blow-up with $a$ classes of $b$ vertices each. All asymptotic errors below concern $n\to \infty$ with the forbidden graphs fixed.

The stability subgraph. We prove the high-minimum-degree multipartite stability subgraph assertion directly from the Erdős-Stone theorem. For $r=1$, the edgeless spanning subgraph suffices. Suppose $r\ge 2$.

First repeatedly remove a vertex whose degree of a vertex is less than $(\alpha -{\epsilon }_n)$ times the current order, where ${\epsilon }_n\to 0$ sufficiently slowly. The Erdős-Stone theorem gives, uniformly for every $K_{r+1}(t)$-free subgraph $J$ of order at most $n$,Indeed, apply the asymptotic bound at large orders; the contribution from bounded or sufficiently small orders is negligible relative to $n^2$. If $m$ vertices survive, the removed edges number at mostComparing with $e(G_n)=\alpha n^2/2+o(n^2)$ shows that ${\epsilon }_n(n^2-m^2)=o({\epsilon }_n{n}^2)$, provided ${\epsilon }_n$ dominates ${\eta }_n$, the initial relative error, and $1/n$. Consequently $m=n-o(n)$. The surviving induced subgraph $G^{\prime }$ satisfies $\delta (G^{\prime })\ge (\alpha -o(1))m$ and $e(G^{\prime })=\alpha m^2/2+o(m^2)$.

By the Erdős-Stone theorem, $G^{\prime }$ contains $K_r(L)$ for some $L=L_n\to \infty$ as slowly as necessary. This follows because $\alpha$ exceeds the extremal number density for each fixed $K_r(L)$ by the positive gap $1/(r(r-1))$. Choose $L$ so slowly that $rL=o(m)$ and ${\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$, and denote its root classes by $A_1,\dots ,A_r$.

An outside vertex having at least $t$ neighbours of a vertex in every $A_i$ determines one choice of a $t$-subset in each $A_i$. At most $t-1$ outside vertices can determine any fixed choice, since otherwise these vertices and the chosen root sets form $K_{r+1}(t)$. Thus at most $(t-1){\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$ outside vertices have this property. Exclude those vertices and the root classes; put each remaining vertex in a class $C_i$ for which it has fewer than $t$ neighbours of a vertex in $A_i$.

Write $\delta (G^{\prime })\ge (\alpha -{\gamma }_n)m$, with ${\gamma }_n\to 0$. Counting missing incidences with $A_i$ givesSince ${\sum }_i|C_i|=m-o(m)$, it follows that $|C_i|=m/r+o(m)$ for every $i$. The total missing incidences from all root vertices to assigned vertices are at most $(1+r{\gamma }_n)Lm$. At least $(L-t+1)(m-o(m))$ of them are incidences with a vertex's own assigned root class. Hence only $o(Lm)$ missing incidences go to other root classes.

Choose ${\rho }_n\to 0$ slowly and discard the $o(m)$ assigned vertices with more than ${\rho }_{n}L$ missing incidences to other root classes. Each remaining vertex of $C_i$ is adjacent to all but at most ${\rho }_{n}L$ vertices of every $A_j$, $j\ne i$. If its class contained a complete bipartite graph $K_{t,t}$, the $2t$ vertices of this copy would have at least $L-2t{\rho }_{n}L\ge t$ common neighbours of a vertex in each other root class. These sets extend the copy to $K_{r+1}(t)$, a contradiction. By the bipartite case of the Erdős-Stone theorem, the number of internal edges in each surviving class is $o(m^2)$.

The surviving graph still has $\alpha m^2/2+o(m^2)$ edges, whereas the total possible cross-class edges, with these balanced classes, is $\alpha m^2/2+o(m^2)$. Thus only $o(m^2)$ cross-class edges are missing. Discard the $o(m)$ vertices missing more than ${\sigma }_{n}m$ cross-class edges, with ${\sigma }_n\to 0$ slowly, and delete all internal edges. The resulting $r$-partite subgraph $H$ has classes $H_i$ of size $n/r+o(n)$ andFor the lower bound, every surviving vertex misses only $o(n)$ vertices outside its class; the upper bound follows from the class sizes. This also records the uniform cross-class error that we need next.

Minimum degree in an extremal graph. Fix $F$ with $\chi (F)=r+1$. Choose $t$ large enough that $F$ embeds in $K_{r+1}(t)$. An extremal $F$-free graph $G$ is therefore $K_{r+1}(t)$-free, and its edge count has the required asymptotics by the Erdős-Stone theorem. For $r\ge 2$ take $H$ as above.

For any vertex $v$, remove $v$ and introduce a new vertex $v^{\ast }$ whose vertex neighbourhood consists precisely of the vertices in $H_2\cup \cdots \cup H_r$ other than $v$. The new degree of a vertex is $\alpha n-o(n)$. This new graph remains $F$-free. Indeed, a new copy of $F$ must use $v^{\ast }$, and all its neighbours of a vertex in that copy lie in the other classes of $H$. There are only boundedly many of them. Each misses only $o(n)$ vertices in $H_1$, so an unused vertex $w\in H_1$ is adjacent to all of them. Replacing $v^{\ast }$ by $w$ would give $F$ in $G-v$, which is impossible.

Extremality now forces $d_G(v)\ge \alpha n-o(n)$, uniformly in $v$. The upper bound for the minimum degree of a graph follows from $\delta (G)\le 2e(G)/n$. For $r=1$, $e(G)=o(n^2)$ already gives $0\le \delta (G)=o(n)$. ThusThis is the minimum degree of an extremal forbidden-subgraph graph principle.

The exact extremal graph for disjoint cliques. DefineThe plus sign denotes the join of graphs. The Turan graph contains no $K_{r+1}$, so every such clique in $J_s(n)$ uses a vertex of $K_{s-1}$. Therefore $J_s(n)$ contains no $s$ vertex-disjoint such cliques, and the extremal number is at least $b_s(n)$.

Induct on $s$, with $s=1$ supplied by the Turan theorem, including its equality characterization. Let $s\ge 2$ and let $G$ be extremal for $s{K}_{r+1}$. The preceding results give $\delta (G)\ge \alpha n-o(n)$ and the $r$-partite subgraph $H$. Keep its classes $H_i$ fixed and assign each of the remaining $o(n)$ vertices to a class in which it has fewest neighbours of a vertex in $H$. Write the resulting classes as $C_i$; all have size $n/r+o(n)$. Choose a positive ${\tau }_n\to 0$ so slowly that ${\tau }_{n}n$ dominates the outside count, every cross-class error in $H$, and every error in the minimum degree of a graph bound.

Suppose some vertex $x\in C_i$ has at least ${\tau }_{n}n$ internal neighbours of a vertex. If $x\notin H$, the assignment rule shows that $x$ has at least ${\tau }_{n}n-o(n)$ neighbours of a vertex in every $H_j$. If $x\in H_i$, it has this many in $H_i$ and $n/r-o(n)$ in the other $H_j$. If $G-x$ contained $s-1$ disjoint $K_{r+1}$, we could choose one vertex in each $N(x)\cap H_j$, successively avoiding those copies and the $o(n)$ missing cross-neighbours of the already chosen vertices. This produces a further $K_{r+1}$ through $x$. For $r=1$, this just chooses an unused neighbour of $x$. Hence $G-x$ is $(s-1)K_{r+1}$-free, and induction givesSince the candidate attains $b_s(n)$, equality holds throughout: $x$ is a universal vertex and $G-x$ is the inductively unique extremal graph. Thus $G$ is isomorphic to $J_s(n)$.

It remains to show that this case must occur. Otherwise all internal vertex degrees are less than ${\tau }_{n}n=o(n)$. Together with the lower bound on $\delta (G)$ and $|C_i|=n/r+o(n)$, this implies that every vertex misses only $o(n)$ vertices outside its own class. If some $C_i$ contains a matching in a graph of $s$ edges, extend its edges one by one to $K_{r+1}$, choosing one vertex from each other class. At every step only $o(n)$ cross-neighbours and boundedly many used vertices are excluded. This gives $s$ disjoint forbidden cliques, a contradiction.

A maximal matching in each class therefore has at most $s-1$ edges, and its at most $2(s-1)$ endpoints form a vertex cover of the internal edges. Their internal vertex degrees are all $o(n)$, so the total internal edge count is $o(n)$. The cross-class edge count is at most $e(T_r(n))$, whenceBut the balanced part sizes of the Turan graph givecontradicting extremality for $s\ge 2$. This argument also works for $r=1$. Consequently, for all sufficiently large $n$,The uniqueness is up to isomorphic graphs, as usual for an extremal graph for disjoint cliques.

The Hall marriage theorem states that a finite bipartite graph with vertex classes $U$ and $V$ has a matching in a graph saturating $U$ if and only ifNecessity is immediate: distinct vertices of $A$ must be matched to distinct vertices of $N(A)$.

For sufficiency, induct on $|U|$. If every nonempty proper $A\subset U$ satisfies the strict bound $|N(A)|\ge |A|+1$, choose any edge $uv$ and delete its endpoints. Every $A\subseteq U\setminus \{u\}$ loses at most the neighbour $v$, so Hall's condition remains true; induction supplies a matching of the smaller graph, to which $uv$ is added.

Otherwise there is a nonempty proper tight set $A\subset U$ with $|N(A)|=|A|$. Hall's condition holds on the induced graph with parts $A,N(A)$, so induction matches $A$. For $B\subseteq U\setminus A$, Hall's condition on $A\cup B$ givesand hence $|N(B)\setminus N(A)|\ge |B|$. Induction therefore matches $U\setminus A$ into $V\setminus N(A)$. The two matchings are disjoint and together saturate $U$, completing the proof through Hall induction through a tight set.

Identify a subset of $[n]$ with its binary characteristic vector. Then $Q$ is the hypercube graph, and every edge changes set size by exactly one. The induced subgraph on $X_{i-1}\cup X_i$ is therefore bipartite with those two levels as its vertex classes.

Let $\mathcal{A}\subseteq X_{i-1}$. Every member of $\mathcal{A}$ has $n-i+1$ neighbours in $X_i$, obtained by adding one element, while every member of $N(\mathcal{A})$ is incident with at most $i$ of these edges. Double-counting the edges between the two families givesSince $i\le n/2$, we have $n-i+1\ge i$, and hence $|N(\mathcal{A})|\ge |\mathcal{A}|$. Hall's theorem yields the requested adjacent-level matching in a Boolean lattice, saturating $X_{i-1}$.

Finally, every chain in a partially ordered set in the Boolean lattice contains at most one member of the middle level $X_{n/2}$. Any chain partition therefore uses at leastchains.

For every $i\le n/2$, choose one of the matchings just constructed and orient its edges upward. These edges partition all levels at or below $n/2$ into chains ending at distinct middle-level sets. Taking complements gives, for every $i\ge n/2$, a matching from $X_{i+1}$ into $X_i$; orienting its edges upward extends those chains through all upper levels. Every subset belongs to exactly one resulting chain and every chain meets $X_{n/2}$ exactly once. Thus this symmetric chain decomposition of a Boolean lattice has one chain per middle-level set, and the minimum is

Vizing theorem states that every finite simple graph of maximum degree $\Delta$ haswhere ${\chi }^{\prime }(G)$ is its edge chromatic number. The lower bound follows because all edges incident with a vertex of degree $\Delta$ need different colours.

For the upper bound, induct on the number of edges. Delete an edge $xy$ and colour the remaining graph with the palette $\{1,\dots ,\Delta +1\}$. We use the Vizing fan lemma: in a partial proper edge colouring with one uncoloured edge $xy$, if the palette has one more colour than the maximum degree, a sequence of fan rotations and two-colour Kempe-chain interchanges makes some colour missing at both ends of the uncoloured edge.

Here is the fan argument. Build a maximal sequence $y_0=y,y_1,\dots ,y_k$ of distinct neighbours of $x$ such that, for $i\ge 1$, the colour on $x{y}_i$ is missing at an earlier fan vertex. Rotating an initial fan segment means moving each colour on $x{y}_i$ to the preceding edge where it is missing; this preserves properness and moves the uncoloured edge to the end of that segment. Choose a colour $\alpha$ missing at $x$ and a colour $\beta$ missing at $y_k$. On the maximal $\alpha$-$\beta$ alternating path from $y_k$, interchange $\alpha$ and $\beta$. If the path does not reach $x$, $\alpha$ is then missing at both $x$ and $y_k$, so rotate the fan and colour its final uncoloured edge $\alpha$. If it reaches $x$, its last edge at $x$ has colour $\beta$. Maximality of the fan forces the other endpoint of that edge to be a fan vertex; rotate up to that vertex first. This breaks the alternating path before $x$, reducing to the preceding case. This proves the fan lemma and extends the colouring to $xy$, completing the induction.

For $K_{n,n}$, label both vertex classes by $\mathbb{Z}/n\mathbb{Z}$ and colour edge $(i,j)$ by $i+j$. Each colour is a perfect matching, so this is an $n$-edge-colouring. Since $\Delta (K_{n,n})=n$, ${\chi }^{\prime }(K_{n,n})=n$. If $r=\max \{m,n\}$, embed $K_{m,n}$ into $K_{r,r}$ and restrict its $r$-edge-colouring. The degree lower bound then gives

Finally, subdividing one edge of $K_{n,n}$ produces $n^2+1$ edges on $2n+1$ vertices while keeping maximum degree $n$. In any proper edge colouring, each colour class is a matching of size at most $n$. An $n$-edge-colouring could therefore colour at most $n^2$ edges, a contradiction. Thus ${\chi }^{\prime }(G)>n$, while Vizing theorem gives ${\chi }^{\prime }(G)\le n+1$, so

The Hall marriage theorem says that a bipartite graph with classes $A,B$ has a matching saturating $A$ if and only ifwhere $N(S)$ is the graph neighbourhood of $S$. Necessity follows because the matching sends the vertices of $S$ to distinct vertices of $N(S)$.

For sufficiency, add vertices $x,y$, join $x$ to every vertex of $A$, and join every vertex of $B$ to $y$. Let $W$ be an $x$-$y$ vertex separator, and write $W_A=W\cap A$ and $W_B=W\cap B$. If an edge joined a vertex of $A\setminus W_A$ to a vertex of $B\setminus W_B$, it would give an $x$-$y$ path avoiding $W$. HenceHall's condition givesand therefore $|W|\ge |A|$. By Menger theorem, there are $|A|$ internally vertex-disjoint $x$-$y$ paths. Each has the form $xaby$ with $a\in A$ and $b\in B$; disjointness makes all the $a$ and all the $b$ distinct. Their middle edges form a matching saturating $A$.

A vertex cover is a set of vertices meeting every edge of a graph. The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$.