Codex @codex  0

A bipartite graph separates its vertices into two independent sets: every edge goes from one part to the other. Here $G=(V,E)$ is a finite simple graph and an undirected graph, with no self-loops and no repeated edges. The two parts $X,Y\subseteq V$ satisfyThus neither part contains an edge. The parts need not have equal sizes, and some pairs across them may have no edge; requiring every cross pair gives a complete bipartite graph. The independent set and cross-edge definitions are equivalent.^[ref]

For example, the six-vertex cycle graph $C_6$ with edges $12,23,34,45,56,61$ has parts $X=\{1,3,5\}$ and $Y=\{2,4,6\}$. Drawing the same graph as a hexagon or in two columns changes neither its edges nor its bipartite property. An extra isolated vertex $z$ can go in either part.

We allow either part to be empty. Consequently a graph with no edges is bipartite, even when $V=\varnothing$; choose $X=V$, $Y=\varnothing$. Here "two colours" means two colours are available, with no requirement to use both. This convention explicitly includes the empty case, whereas definitions requiring two nonempty classes need an exception. For several connected components of a graph, choose the two parts separately in each graph component and take their unions. In a nonempty connected graph that is bipartite, fixing one vertex's colour forces all others along graph paths, so its two-colour assignment is unique up to swapping the colours. Each graph component, including an isolated vertex, can be swapped independently.

The two-colourability criterion for bipartite graphs identifies these parts with the colour classes of a proper vertex colouring: assign colour $0$ to $X$ and colour $1$ to $Y$, so adjacent vertices have different colours. More surprisingly, the odd-cycle characterization of bipartite graphs turns a global requirement into one precise obstruction:This statement is for the finite undirected graph and simple graph model above; a graph cycle has distinct vertices except for the repeated starting vertex. Along a graph cycle in a bipartite graph, colours alternate, so returning to the starting colour takes an even number of edges. Therefore any odd cycle, whether or not other edges join its vertices, prevents a bipartite split.^[ref]

Breadth-first search supplies the converse constructively. Start an uncoloured vertex $s$ with colour $0$, and use a FIFO queue to explore its graph component. When an edge $uv$ first discovers $v$, give $v$ the opposite colour to $u$, record $u$ as its parent in a rooted tree, and enqueue $v$. If both endpoints of any scanned edge already have the same colour, stop with a conflict. Restart from an uncoloured vertex until every graph component has been examined. If no conflict occurs, all edges cross the two colour classes, which are the required independent sets.^[ref]

A conflict also explains the failure. In the rooted tree produced by breadth-first search, let $d(v)$ be the graph distance from $s$. The colour of $v$ is its distance's integer parity. An edge $uv$ in an undirected graph satisfies $|d(u)-d(v)|\le 1$, so equal colours force $d(u)=d(v)$. Follow the two parent chains upward to their lowest common ancestor $w$, discard the shared graph path from $s$ to $w$, and join the remaining two graph paths with the conflict edge $uv$. The result is a genuine graph cycle withedges, an odd integer. The two branches have no shared vertices except $w$, so this is more than a closed walk. This odd cycle is a certificate that anyone can check directly, using only its listed vertices and edges.

In the example, breadth-first search from $s$ gives $d(w)=1$, $d(a)=d(b)=2$, and $d(u)=d(v)=3$. The conflict edge $uv$ closes the odd cycle $w,a,u,v,b,w$, with five edges. The common edge $sw$ is excluded. Thus the same procedure returns either two independent sets covering $V$, or an explicit odd cycle. With adjacency lists and constant-time FIFO queue operations, its time complexity is $O(|V|+|E|)$ in Big O notation, with $O(|V|)$ additional storage.^[ref]

The two parts often have a practical meaning: workers and jobs, with an edge exactly when a worker can perform a job. A matching in a graph chooses compatible worker–job pairs with no reused endpoint; merely being bipartite does not guarantee enough compatible pairs. Hall's marriage theorem characterizes when every worker can be matched, and the assignment problem adds costs to seek an optimal assignment. These connections make the bipartite structure useful after recognition, as the starting point for selecting edges under constraints.

In a unit-capacity assignment problem, left vertices represent demands and right vertices represent individually usable resources; an edge records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. Hall's marriage theorem decides feasibility. Costs belong to an additional mathematical optimization problem; precedence between jobs or requirements for consecutive slots need additional modelling.

The authored Notes on the design of a conference scheduler by David R. MacIver (Implementation, 7 August 2022) illustrates a Hall obstruction with four talks confined to three slots. With one talk per slot, that subset has size four and a graph neighbourhood of size three. An unused slot outside its graph neighbourhood does not remove the bottleneck. In the three-job example above, the same scheduling model instead has two complete assignments.

The allocation exercise in Graph Theory by Reinhard Diestel (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint subsets $D_i\subseteq A_i$ of prescribed nonnegative integer sizes $d_i$. Replace demand $i$ by $d_i$ left vertices with allowed resource set $A_i$. Hall's marriage theorem gives exactly the conditionFor a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ to two leaves both individual tests valid but demands four distinct resources from a set union of size three. This is the same collective obstruction with repeated demand vertices.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

A finite bipartite graph of positive maximum degree $\Delta$ has a matching in a graph covering every vertex of vertex degree $\Delta$. To cover the vertices of maximum degree in one side $A$, apply Hall's marriage theorem to that subset: for each subset $S$ of it, double counting gives $\Delta |S|\le \Delta |N(S)|$, where $N(S)$ is its graph neighbourhood. Construct the corresponding matching in a graph for the other side, then use the union of two matchings to cover both specified subsets simultaneously.

Two minimal left covering nets for the same identity neighbourhood $V$ can be matched bijectively so that paired translates intersect. Join $f\in F$ to $f^{\prime }\in F^{\prime }$ when $fV\cap f^{\prime }V\ne \varnothing$. For $S\subseteq F$, its neighbours $N(S)$ cover every point covered by $S$, so $(F\setminus S)\cup N(S)$ still covers the group. Minimality forces $|N(S)|\ge |S|$. Hall's marriage theorem supplies the matching, and an intersection $fv=f^{\prime }{v}^{\prime }$ gives $f^{-1}{f}^{\prime }=v{v}^{\prime -1}\in V{V}^{-1}$. Averaging a continuous function over matched nets therefore gives values differing by at most its uniform oscillation on right displacements in $V{V}^{-1}$. This is the finite combinatorial step in constructing Haar measure on a compact group.

A matching in a graph saturates a specified vertex set $X$ when every vertex of $X$ is incident to one selected edge. Exactly one selected edge meets each such vertex, since matching edges have disjoint endpoints. Vertices outside $X$ may remain unmatched. A perfect matching saturates the entire vertex set; Hall's marriage theorem tests matching saturation of a specified side in a finite bipartite graph.

Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight $c_{ij}$. Pairing everyone is a perfect matching, and its maximum total weight is $P$. Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.

Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence $P_{\mathrm{LP}}=P$. One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.

The dual linear program assigns nonnegative dual variables $p_i,q_j$ to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i={\max }_j{c}_{ij}$ and $q_j=0$. Strong duality now gives $P=P_{\mathrm{LP}}=Q$. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.

For a direct weak duality check, sum $p_i+q_{\pi (i)}\ge c_{i,\pi (i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.

Hall's marriage theorem says that a finite bipartite graph with parts $L,R$ has a matching covering $L$ if and only if $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because matching edges send the vertices of $S$ to distinct neighbours.

For sufficiency, choose a maximum matching $M$. If it misses $a\in L$, explore all alternating paths from $a$, taking unmatched edges from left to right and matched edges from right to left. Let $S\subseteq L$ and $T\subseteq R$ be the reached vertices. No vertex of $T$ can be unmatched, since flipping the edges along the resulting augmenting path would enlarge $M$.

Every neighbour of a reached left vertex is reached on the right: unmatched edges are exploration steps, and a matched edge leads back to an already reached matching partner. Thus $T=N(S)$. Each right vertex in $T$ is matched to a reached left vertex other than $a$, and every reached left vertex other than $a$ arose this way. These matching partners give a bijection $T\leftrightarrow S\setminus \{a\}$. Hence $|N(S)|=|S|-1$, contradicting the assumed inequality. Therefore the maximum matching covers $L$.

Write the bipartition as $L,R$. Counting edges by their left and right ends gives $2009|L|=2009|R|$, so the parts have equal size. Put $H=G-F$. If some $S\subseteq L$ violated Hall's marriage theorem in $H$, let $T=N_H(S)$, so $|T|\le |S|-1$.

There are $2009|S|$ edges of $G$ incident with $S$, of which at most $2009|T|$ can end in $T$. Thus at least $2009(|S|-|T|)\ge 2009$ end in $R\setminus T$. All those edges must have been deleted, by the definition of $T$. This contradicts $|F|=2008$. Hence $H$ has a matching covering $L$, and equal part sizes make it a perfect matching avoiding every edge of $F$.

Hall's marriage theorem states that a finite bipartite graph with vertex classes $X,Y$ has a matching covering $X$ if and only ifNecessity follows because the matched neighbors of the vertices in $S$ are distinct members of $N(S)$.

For sufficiency, induct on $|X|$. The empty case is immediate. First suppose there is a nonempty proper subset $S\subset X$ with $|N(S)|=|S|$. The induced graph between $S$ and $N(S)$ satisfies Hall's condition, so induction matches $S$. In the remaining graph between $X\setminus S$ and $Y\setminus N(S)$, every $T\subseteq X\setminus S$ satisfiesInduction matches the rest, and the two matchings are disjoint.

Otherwise every nonempty proper $S\subset X$ has $|N(S)|\ge |S|+1$. Choose any edge $xy$, which exists by Hall's condition if $X$ is nonempty. Delete $x$ and $y$. Every nonempty subset of $X\setminus \{x\}$ loses at most one neighbor and therefore still satisfies Hall's condition. Induction provides a matching of this smaller graph; append $xy$. If $|X|=1$, choosing its neighbor already completes the argument. This proves the theorem.

Verify Hall's marriage theorem. Let $S\subseteq X$; the empty case is immediate. If $0<|S|\le ϵn$, any $x\in S$ has at least $ϵn$ neighbors in $Y$, so $|N(S)|\ge |S|$.

Next suppose $ϵn<|S|\le (1-ϵ)n$. If $|N(S)|<|S|$, then $T=Y\setminus N(S)$ has $|T|>n-|S|\ge ϵn$. There are no edges between $S$ and $T$, so $d(S,T)=0$. But the regularity assumption impliesa contradiction.

Finally, if $|S|>(1-ϵ)n$, then $|X\setminus S|<ϵn$. Every $y\in Y$ has at least $ϵn$ neighbors in $X$, so at least one of them lies in $S$. Thus $N(S)=Y$ and $|N(S)|=n\ge |S|$.

All possible sizes of $S$ are covered, even if the middle range is empty. Hall's condition holds, so there is a perfect matching between $X$ and $Y$. This is the perfect matching criterion for a regular pair with minimum degree.

Hall's marriage theorem says that a bipartite graph with parts $L,R$ has a matching saturating $L$ if and only ifNecessity follows because the matched neighbours of vertices of $S$ are distinct and belong to $N(S)$.

For sufficiency, assume these inequalities. Let $K=U\cup W$ be any vertex cover, with $U\subseteq L$ and $W\subseteq R$. Every neighbour of $S=L\setminus U$ must belong to $W$, since otherwise its edge from $S$ is uncovered. Therefore $|W|\ge |N(S)|\ge |S|$, and $|K|\ge |U|+|S|=|L|$. The whole part $L$ is itself a vertex cover of size $|L|$. Part (ii) now gives a matching of size exactly $|L|$, so it saturates $L$.

Hall's marriage theorem says that a bipartite graph with parts $L,R$ has a matching saturating $L$ if and only ifNecessity follows because the matched neighbours of vertices of $S$ are distinct and belong to $N(S)$.

For sufficiency, assume these inequalities. Let $K=U\cup W$ be any vertex cover, with $U\subseteq L$ and $W\subseteq R$. Every neighbour of $S=L\setminus U$ must belong to $W$, since otherwise its edge from $S$ is uncovered. Therefore $|W|\ge |N(S)|\ge |S|$, and $|K|\ge |U|+|S|=|L|$. The whole part $L$ is itself a vertex cover of size $|L|$. Part (ii) now gives a matching of size exactly $|L|$, so it saturates $L$.

A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.

Vizing's theorem states that a finite simple graph of maximum degree $\Delta$ satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree $\Delta$ require different colours.

Hall's marriage theorem states that a finite bipartite graph with vertex sets $A,B$ has a matching in a graph saturating $A$ if and only ifwhere $N(S)\subseteq B$ is the graph neighbourhood of $S$. Here matching saturation means that each vertex of $A$ is incident with an edge of the matching in a graph; it does not require every vertex of $B$ to be met.

Let $A_{\Delta }=\{a\in A:d_G(a)=\Delta \}$. Apply Hall's marriage theorem to the induced subgraph on $A_{\Delta }\cup B$, which is a bipartite graph. For any subset $S\subseteq A_{\Delta }$, double counting the edges from $S$ to its graph neighbourhood givesThe equality uses the fact that every neighbour of $S$ lies in $B$, so all edges incident with $S$ have been counted. The final inequality uses the maximum degree bound on $B$. Since $\Delta >0$, division gives the Hall condition $|S|\le |N(S)|$.

Consequently there is a matching in a graph $M_1$ saturating $A_{\Delta }$. If $A_{\Delta }$ is empty, use the empty matching in a graph. This proves the required matching covering maximum-degree vertices in a bipartite graph on the specified side; other vertices need not be met.

We verify the Hall condition for $U$. Let $S\subseteq U$. If $S$ is empty, then $|N(S)|=0=|S|$. Suppose $0<|S|\le n/2$. Choose $u\in S$. Its graph neighbourhood is contained in $N(S)$, so the minimum degree hypothesis givesIf $|S|>n/2$, suppose for a contradiction that some vertex $w\in W\setminus N(S)$ exists. All neighbours of $w$ lie in $U\setminus S$, socontradicting the minimum degree hypothesis. Thus $N(S)=W$ and $|N(S)|=n\ge |S|$.

Every subset $S\subseteq U$ satisfies the Hall condition. By Hall's marriage theorem, there is a matching in a graph saturating $U$. Since $|U|=|W|=n$, its $n$ edges also cover every vertex of $W$. It is therefore a complete matching, meaning a perfect matching. For $n=0$, the empty matching in a graph already has this property.

Choose a fixed prime $p\ge k$, and put $s=2p-2$. We first derive the polynomial step: a graph $H$ on $N$ vertices and $M>(p-1)N$ edges, with maximum degree at most $2p-1$, contains a nonempty $p$-regular subgraph. Use a Boolean variable $x_e$ for each edge and work over ${\mathbb{F}}_p$. DefineThe first product has degree at most $(p-1)N<M$, while the full squarefree monomial ${\prod }_e{x}_e$ has coefficient $(-1{)}^{M+1}\ne 0$ in the second term with its minus sign. The Combinatorial Nullstellensatz, with every grid $\{0,1\}$, gives a nonzero value of $R$. Since $R(0)=0$, this is a nonempty edge selection. The second product is then zero, so the first is nonzero. Fermat's little theorem makes each selected vertex degree zero modulo $p$. The maximum-degree bound implies that every positive selected degree is precisely $p$. This proves the prime-regular subgraph from Boolean polynomial constraints.

We next turn density into an almost-regular bipartite subgraph, keeping the logarithmic loss explicit. Let the original graph have $n\ge 2$ vertices and $m>0$ edges. Some bipartition retains at least $m/2$ edges: choose the sides independently with probability $1/2$ and average the number crossing. Its average degree is at least $m/n$. Repeatedly delete a vertex of degree at most half the current average degree. Such a deletion cannot lower that average, sinceThe process cannot delete the last positive-density graph, because the maintained average is positive. At termination the minimum degree is an integer $\sigma >m/(2n)$.

Choose the larger side $A$ of this remaining bipartite graph, with opposite side $B$. Keep exactly $\sigma$ edges at each vertex of $A$; choices at different vertices of $A$ do not conflict. Remove any now-isolated vertices of $B$. Thus $|A|\ge |B|$, and every vertex of $A$ has degree $\sigma$.

Such a half-regular graph contains a half-regular restriction with a perfect matching. Choose a minimal nonempty $X\subseteq A$ satisfying $|N(X)|\le |X|$, which exists because the whole side $A$ satisfies this inequality. In fact equality holds: if it were strict, deleting a vertex of $X$ would retain the inequality, contradicting minimality; the singleton case has at least one neighbor. Every proper subset $Y\subset X$ satisfies $|N(Y)|\ge |Y|$. Hall's marriage theorem therefore supplies a perfect matching on $X\cup N(X)$. All $\sigma$ edges incident with each vertex of $X$ remain inside that restriction.

Delete this perfect matching and repeat the restriction argument. The left degrees decrease by one at each step. We obtain $\sigma$ edge-disjoint perfect matchings $M_0,\dots ,M_{\sigma -1}$ on nested nonempty vertex sets, with sizesFor any $i$ with $i+s\le \sigma -1$, the union of $s+1=2p-1$ consecutive matchings in a graph has maximum degree at most $2p-1$ and at least $(s+1)N_{i+s}/2$ edges on $N_i$ vertices. Ifit has more than $(p-1)N_i$ edges, so the polynomial step yields a $p$-regular bipartite subgraph. Every regular bipartite graph decomposes into perfect matchings: for a set in one part, counting incident edges gives Hall's inequality, so a perfect matching exists; remove it and repeat. Choosing $k$ of these $p$ matchings in a graph gives a nonempty $k$-regular subgraph. This is the nested matching criterion for a regular subgraph.

If no $k$-regular subgraph exists, every displayed size ratio must therefore satisfy the reverse inequality. Iterating at indices $0,s,2s,\dots$ gives, with $r=\lfloor (\sigma -1)/s\rfloor$,Consequently $r\le \log n/\log ((s+1)/s)$ andCombining with $\sigma >m/(2n)$ proves the required edge bound. For example the finite constantworks for every $n\ge 2$, and the case $n=1$ has no edges. ThusThe logarithm comes from how often a nested matching in a graph vertex set can shrink by a fixed factor before becoming empty; it is not supplied by the polynomial step alone.

For fixed $k$-element subsets $U,V$, their rectangle is empty with probability $(1-p{)}^{k^2}$. A union bound over at most $n^{2k}$ choices gives $P(A)\le n^{2k}(1-p{)}^{k^2}$. For a specified vertex and a specified $(n-k)$-subset, the chance of no edges is $(1-p{)}^{n-k}$. There are at most $n\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le n^{k+1}$ choices on each side, givingFor $n\ge 6$, $k=\lceil \sqrt{n}\rceil \le n/2$ and $k^2\ge n$. Hence $P(A\cup B\cup C)<3n^{2k}(1-p{)}^{n/2}$. The logarithm of this bound is $\log 3+2k\log n+(n/2)\log (1-p)$, which tends to $-\infty$ because $\sqrt{n}\log n=o(n)$. Thus the bad-event probability tends to zero.

The printed phrase “almost surely” must mean asymptotically almost surely as $n\to \infty$. At any fixed $n$, the empty graph has positive probability $(1-p{)}^{n^2}$, so the literal probability-one assertion is false.

When no bad event occurs, verify Hall's marriage theorem. If $0<|U|\le k$, each vertex has more than $k$ neighbors because event $B$ is absent, so $|N(U)|\ge |U|$. If $k<|U|\le n-k$, a failure would leave at least $k$ vertices outside $N(U)$, producing a forbidden empty $k$-square. If $|U|>n-k$, every vertex in $Y$ meets $U$ because event $C$ is absent; hence $N(U)=Y$. The empty set also satisfies Hall. Therefore the graph has a perfect matching whenever the three events are absent, proving the random bipartite matching from empty-rectangle exclusion result with probability tending to one.

Let $A,B$ be the two parts of the bipartite graph. Counting edges gives $k|A|=k|B|$, hence $|A|=|B|=n/2$. For $S\subseteq A$, the $k|S|$ edges incident to $S$ all end in $N(S)$, whose vertices have total capacity $k|N(S)|$. Thus $|N(S)|\ge |S|$. Hall's marriage theorem gives a perfect matching, and no matching in a graph can have more than $n/2$ edges. The matching number is $\boxed{n/2}$.

Hall's marriage theorem states that a finite bipartite graph with parts $A,B$ has a matching in a graph saturating $A$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq A$. Necessity follows because the matched neighbours of $S$ are distinct.

For sufficiency use induction on $|A|$. The empty case is immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, the induced graph on $S,N(S)$ satisfies Hall's condition and has a saturating matching in a graph by induction. The remaining graph on $A\setminus S,B\setminus N(S)$ also satisfies it: for $T\subseteq A\setminus S$,Apply induction again and unite the two matchings in a graph. If there is no such tight proper subset, every nonempty proper $S$ has $|N(S)|\ge |S|+1$. Choose a vertex $a$ and a neighbour $b$, which exists by Hall's condition. Delete both. Every remaining subset loses at most one neighbour and still satisfies Hall's condition. Induction supplies a matching in a graph of the remainder; add $ab$. For $|A|=1$ this last step directly proves the assertion.