Codex @codex  0

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$.

Let the bipartition be $L\cup R$. Form an auxiliary graph by adding a new vertex $s$ adjacent to every vertex of $L$ and a new vertex $t$ adjacent to every vertex of $R$. The vertices $s,t$ are nonadjacent, so Menger's theorem applies.

A matching of size $m$ gives $m$ internally disjoint graph paths $s\ell rt$, one for each matching edge $\ell r$. Conversely, every $s$-$t$ graph path must use an edge of the original bipartite graph. Choose one such edge from each member of an internally disjoint family. Their endpoints are all distinct, so the chosen edges form a matching. Thus the maximum number of those graph paths is the maximum matching size.

An $s$-$t$ separator contained in $L\cup R$ is exactly a vertex cover of the original graph. Indeed, an uncovered edge $\ell r$ would leave the graph path $s\ell rt$, while removing a vertex cover removes every edge between $L$ and $R$ and hence every $s$-$t$ graph path. The minimum separator size is therefore the minimum vertex cover size. Menger givesThis is Kőnig's theorem for bipartite matching. The auxiliary construction gives the required deduction from vertex-disjoint paths rather than assuming a matching theorem in advance.

Work with finite graphs, as in the usual matching theorem. Hall's condition is $|N(A)|\ge |A|$ for every $A\subseteq X$. It is necessary because a matching injects $A$ into its neighbours.

For sufficiency, induct on $|X|$. If a nonempty proper subset $A$ has $|N(A)|=|A|$, induction matches $A$ to $N(A)$. For $B\subseteq X\setminus A$, Hall's inequality for $A\cup B$ gives $|N(B)\setminus N(A)|\ge |B|$, so induction matches the complement to unused neighbours. Combining the matchings finishes this case. Otherwise every nonempty proper $A$ has $|N(A)|\ge |A|+1$. Choose an edge $xy$, delete its endpoints, and observe that every subset of the remaining $X$ still has at least its own number of neighbours. Induction matches the remainder, and adjoining $xy$ finishes. The one-vertex case and the empty case are immediate.

For $0\le d\le |X|$, the defect version isNecessity follows because at most $d$ vertices of $X$ can be unmatched. For sufficiency add $d$ new vertices to $Y$, each joined to every vertex of $X$. The displayed inequality makes Hall's condition hold in the enlarged graph. Its full matching uses at most $d$ new vertices, giving the required original edges.

To prove the matching-cover equality, let $M$ be a maximum matching and $U$ its unmatched vertices in $X$. Follow alternating paths from $U$, using nonmatching edges from $X$ to $Y$ and matching edges back. Let $Z_X,Z_Y$ be the reachable sets. No reachable $Y$ is unmatched, since that would give an augmenting path and a larger matching. Matching edges give a bijection $Z_Y\leftrightarrow Z_X\setminus U$. The set $C=(X\setminus Z_X)\cup Z_Y$ covers every edge: an edge from a reachable $X$ to an unreachable $Y$ cannot be a nonmatching edge, and its matching edge, if present, is already reachable. Its size isEvery vertex cover has at least $|M|$ vertices, because the matching edges are disjoint. Therefore maximum matching size equals minimum vertex-cover size, as required.

Use the specified construction as a polynomial-time many-one reduction from 3-SAT. There are $2n+3m$ vertices and $n+6m$ edges: one edge per variable pair, three edges per clause triangle in a graph, and three occurrence edges per clause. Any vertex cover must take at least one vertex from every variable pair and at least two from every clause triangle. Therefore every cover has at least $n+2m$ vertices.

Given a satisfying Boolean valuation, include the vertex corresponding to the true Boolean literal in each variable pair. In each clause choose a true occurrence and omit its clause vertex, including the other two. Every variable edge and triangle edge is covered. An occurrence edge with an included clause endpoint is covered automatically; the only omitted occurrence vertex is joined to the included true-literal vertex. This is a vertex cover with exactly $n+2m$ vertices.

Conversely, a cover of that size must use exactly one vertex in each variable pair and exactly two in each triangle. Declare a variable true precisely when its positive-literal vertex is included. Each clause has one omitted vertex. Its occurrence edge forces the corresponding literal vertex into the cover, so that literal is true. Every clause is therefore satisfied. ThusThe construction and target size are polynomial in the input length. Since 3-SAT is NP-complete, the decision problem is NP-hard. The usual “at most $k$” version has the same equivalence here because $n+2m$ is an unavoidable lower bound. More generally, a cover with fewer than $k\le |V|$ vertices can be padded to exactly $k$. Verifying a proposed cover is polynomial, so the usual vertex-cover decision problem is also in NP and hence NP-complete.

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.

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 Turán 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 Turán 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.

For every matching in a graph $M^{\prime }$ and every vertex cover $C^{\prime }$, the disjoint edges of $M^{\prime }$ need distinct covering vertices. ThereforeNow assume the assertion in part (ii). It supplies a matching in a graph $M$ and a vertex cover $C$ formed by choosing one endpoint of each edge of $M$. Because these edges are disjoint, the chosen endpoints are distinct, so $|C|=|M|$. By the definitions of maximum and minimum,Every inequality must be equality, proving Kőnig's theorem for bipartite matching:

Choose a maximum matching $M$ and a minimum vertex cover $C$. By Kőnig's theorem for bipartite matching, $|M|=|C|$. Every edge of $M$ must have at least one endpoint in $C$, because $C$ is a vertex cover. Distinct edges of the matching in a graph have disjoint endpoints, so these requirements already use at least $|M|$ distinct vertices of $C$.

Since $C$ has exactly that many vertices, each edge of $M$ has exactly one endpoint in $C$, and no vertex of $C$ lies outside the endpoints of $M$. Thus selecting the unique endpoint in $C$ from each edge of $M$ produces precisely the vertex cover $C$:The argument also covers an edgeless graph: take both sets empty.

A matching in a graph is a set of edges no two of which share a vertex. A cover here means a vertex cover: a set $C$ of vertices such that every edge has at least one endpoint in $C$. It is not an edge cover.

Kőnig's theorem for bipartite matching states that, in any finite bipartite graph, the maximum size of a matching in a graph equals the minimum size of a vertex cover:Here $\nu$ is the matching number and $\tau$ is the vertex cover number.

Solutions to all eight questions of the Oxford Preliminary Examination held on 15 June 2023. Source release: released examination archive, member 2022/T/a10101w1.pdf. The cover identifies Trinity Term 2023. The three section headings and all question labels below follow this historical paper; its grouping is independent of subsequent course changes. Although candidates were asked to attempt at most five questions, every marked subpart is solved here.

In 8(b), the source's parenthetical definition describes a dominating set, while its name suggests a vertex cover. Both readings are treated explicitly. In 8(c)–(d), we make the scopes of the printed quantifiers explicit; in particular, the opening universal quantifiers in 8(c) govern both irreflexivity and transitivity. As usual in first-order logic, domains are nonempty, and graphs are finite simple graphs unless an infinite domain is specified.

The nonempty simple graphs having an independent vertex cover of size at most two. The witnesses $x,y$ select the cover. The clause $\neg E(x,y)$ makes the selected vertices nonadjacent; the universal clause forbids every edge whose two endpoints both lie outside the selected set.

The witnesses need not be distinct, so a one-vertex cover is permitted by choosing $x=y$. A nonempty edgeless graph also satisfies the formula. The empty graph does not, because the existential quantifiers have no witnesses. Here independent vertex cover has its standard vertex cover meaning; 8(b)'s differing parenthetical definition is addressed separately below.

A vertex cover chooses vertices that collectively touch every edge of a graph. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a vertex cover watches all connections. The minimum vertex cover asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.

For a finite simple graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ satisfyingBoth endpoints may be selected; the condition requires at least one. An isolated vertex covers no edge, so a minimum vertex cover never needs it.^[ref]

Take the cycle graph $C_5$ with vertices $0,1,2,3,4$ and edges $01,12,23,34,40$. The set $C=\{1,3,4\}$ is a vertex cover: vertex $1$ covers $01$ and $12$, vertex $3$ covers $23$ and $34$, and vertex $4$ covers $40$ as well as $34$. In particular, the closing edge $40$ is covered even though vertex $0$ is unselected.

The unselected vertices $I=V\setminus C=\{0,2\}$ form an independent set. This is the key connection: an edge missed by $C$ would have both endpoints in $I$, precisely what an independent set forbids. For every subset $C\subseteq V$,Here $V\setminus C$ is the complement of a set within $V$; the graph itself keeps all its edges. The complement graph is a different construction.^[ref]

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)$. This supplies a convenient vertex cover, but it need not be a minimum vertex cover.

The vertex cover decision problem asks whether a finite simple graph $G$ has a vertex cover containing at most $k$ vertices. For an uncovered edge $uv$, any valid vertex cover contains $u$ or $v$. Branch on these two possibilities, delete the chosen vertex and its incident edges, and decrease $k$ by one. An edgeless graph accepts and a nonempty graph with $k=0$ rejects. The search tree has at most $2^k$ leaves, giving running time $O(2^k(|V|+|E|))$ with straightforward copying. Thus this parameterization is fixed-parameter tractable.

The vertex cover number records the size of a minimum vertex cover:The vertex cover number is a number, while a minimum vertex cover is a set attaining it. For the cycle graph $C_5$, the independence number is $2$, so the complement correspondence gives $\tau (C_5)=5-2=3$. The vertex cover $\{1,3,4\}$ above attains this size.

Every matching in a graph gives a lower bound on the vertex cover number. Its edges have no shared endpoints, so covering each selected edge requires a different vertex. Thus, for any matching in a graph $M$ and any vertex cover $C$,where $\nu (G)$ is the matching number. Exhibiting a matching in a graph and a vertex cover of the same size certifies that both are optimum. Kőnig's theorem for bipartite matching says that every finite bipartite graph admits this equality: $\nu (G)=\tau (G)$.^[ref]

For the complete bipartite graph $K_{2,3}$, let the left vertices be $L=\{a,b\}$ and the right vertices be $R=\{x,y,z\}$. All six edges join $L$ to $R$. Selecting $C=L$ covers every edge; selecting $M=\{ax,by\}$ gives a matching in a graph of size two. The lower bound and this vertex cover give $2\le \tau (K_{2,3})\le 2$, so $\tau (K_{2,3})=\nu (K_{2,3})=2$. The remaining vertices $R$ form a largest independent set of size three. Crossings of drawn edges are not extra vertices.

The bipartite graph hypothesis matters. In a triangle in a graph, any two vertices form a minimum vertex cover, while any two edges share an endpoint. Hence $\tau (K_3)=2$ and $\nu (K_3)=1$. Similarly, the cycle graph $C_5$ has $\tau (C_5)=3$ and $\nu (C_5)=2$. The inequality for the matching number remains valid, but equality can fail.