Codex @codex  0

To establish strong NP-completeness, use an explicit adjacency matrix encoding for a finite simple graph, with enough length information to recover its number $N$ of vertices. Let $\mathrm{bin}(k)$ be the canonical binary numeral system representation of the nonnegative integer $k$. Defineand, using the unary numeral system for $k$,The surrounding pairing syntax delimits the two components, so the empty unary field can encode $k=0$ if zero is included in the convention for natural numbers. Malformed descriptions are excluded from both formal languages.

Fix a unary no-instance $u_0$, for example one isolated vertex with requested size $2$. The polynomial-time many-one reduction isMap malformed inputs to $u_0$ too. When $k\le N$, only the numerical representation changes, so the existence of a $k$-clique is unchanged. When $k>N$, the original instance is false, since a subset of vertices cannot be larger than the whole vertex set; $u_0$ is false as required.

The important size bound is $k\le N$ in the branch that writes $1^k$. The original explicit graph description already has length at least $N$, so the output has polynomial length and can be written in polynomial time. If a huge binary numeral system value $k$ is supplied, compare it with $N$ using its digit length and, when needed, a digit comparison; do not first allocate or print $k$ symbols. Merely replacing an unrestricted binary $k$ by $1^k$ would not be a valid polynomial-time reduction.

Thus ${\mathcal{L}}_{\mathrm{Clique}}{\le }_p{\mathcal{L}}_{u\mathrm{Clique}}$. The unary version is in NP by the same clique complexity certificate verification, and is NP-hard by this polynomial-time many-one reduction and part (e). ThereforeThis conclusion uses the conventional explicit graph encoding; a succinct circuit description of a graph would be a different input representation and a different problem.

Consider any edge $\{u,v\}$ of the simple graph. One endpoint comes first in the permutation $\sigma$; suppose it is $u$. Then $v$ has a graph neighbour preceding it, namely $u$, so $v\notin S(\sigma )$. Therefore no edge has both endpoints in $S(\sigma )$:This argument uses only the order of the endpoints, with no random choice required.

Let $Z$ be the set of isolated vertices of the finite simple graph $G=(V,E)$. Introduce a nonnegative integer $x_v$ for every vertex. Use the integer programEvery nonisolated vertex belongs to an edge, whose inequality and the other endpoint's nonnegativity already imply $x_v\le 1$. The explicit bounds on $Z$ therefore make all variables binary. For an integer feasible point, $S=\{v:x_v=1\}$ is an independent set, and its cardinality is the objective. Conversely the indicator vector of any independent set is feasible. Thus the optimal value is the maximum independent set size. Including the isolated-vertex bounds is essential for an arbitrary graph; without them the formulation would be unbounded whenever an isolated vertex is present.

The vertex cover decision problem takes a finite simple graph $G$ and a nonnegative integer $k$, and asks whether there is a vertex cover of cardinality at most $k$. The optimization problem asks for a minimum vertex cover, with cost equal to its cardinality.

For the decision problem, if there are no edges, accept; if there is an edge but $k=0$, reject. Otherwise choose an edge $uv$ and branch: either include $u$ and recurse on $G-u$ with budget $k-1$, or include $v$ and recurse on $G-v$ with budget $k-1$. Accept if either branch accepts. Every vertex cover contains at least one endpoint of $uv$, so every possible solution is retained by at least one branch. Conversely, adding the selected endpoint to a vertex cover returned by the smaller instance covers all original edges. This proves correctness by induction on the remaining budget.

The search tree has depth at most $k$ and at most $2^k$ leaves. Processing each node in $O(|V|+|E|)$ time gives $O(2^k(|V|+|E|))$ running time, establishing fixed-parameter tractability.

For optimization, greedily build a maximal matching $M$: repeatedly select an edge and discard every edge touching either endpoint. Return the set $C$ of all endpoints of $M$. Any edge with neither endpoint in $C$ could be added to $M$, contradicting maximality; thus $C$ is a vertex cover. Since the edges of a matching in a graph have pairwise disjoint endpoint sets, every vertex cover must contain at least one different vertex for each of them. ThereforeThe greedy construction takes polynomial time, and can be implemented in $O(|V|+|E|)$ with adjacency lists. It needs only a maximal matching, not a maximum matching.

Worked solutions to all three questions of the Oxford examination held on 25 May 2023. Source release: released examination archive, member 2022/T/a18330w1.pdf; the cover identifies the examination as Trinity Term 2023. Numbering follows the source PDF, pages 2–4. The examination asks candidates to choose two questions; all three are solved here.

We use finite simple graphs throughout the graph arguments. In Question 1(c), $V$ must be nonempty for the stated minimum to exist. In Question 3(d), an edge cover exists only when there is no isolated vertex; for a nonempty connected graph this excludes the one-vertex graph. These minor domain qualifications are made explicit in the affected solutions.

Choose a perfect matching $M$ from (i). Every vertex has exactly two incident edges in $E\setminus M$, so this spanning subgraph is a disjoint union of graph cycles. Orient each graph cycle cyclically, and let $s(v)$ be the next vertex after $v$ along its oriented graph cycle.

For each $uv\in M$, take the three-edge sequenceIts four vertices are distinct. Each $s(u)\ne u$ and $s(v)\ne v$ because the graph is a simple graph. Also $s(u)\ne v$ and $s(v)\ne u$, since $uv$ belongs to $M$, rather than $E\setminus M$. Finally $s(u)\ne s(v)$ because the successor map $s$ is a bijection on the disjoint graph cycles. Thus this is a graph path of length exactly three.

Every edge of $M$ is used once as a middle edge. Every edge of $E\setminus M$ is used once as the outgoing edge of its tail, whose unique edge of $M$ determines which graph path contains it. Hence these graph paths are pairwise edge-disjoint and cover $E$. This is the three-edge path decomposition from a perfect matching.

The simplicial intersection conditions prohibit loops and multiple edges between the same pair of vertices, so the one-skeleton is a simple graph andUsing the preceding identity gives $V^2-7V+6\chi \ge 0$. A closed surface has $\chi \le 2$ and a simplicial triangulation has $V\ge 4$. The smaller root is at most three, so this inequality forces $V$ to lie above the larger root:For completeness, fewer than four vertices could give at most one triangle under the intersection rules, which cannot form a closed surface.

Solutions to all three questions of the graph theory course of the University of Oxford Part B examination, sat on 15 June 2023. Source: original released PDF, bundle pages 243–244; paper pages 1–2. Throughout, graphs are finite simple graphs unless a construction explicitly permits parallel edges.

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.

For even $r\ge 2$, take the complete graph $K_{r+1}$. It is an $r$-regular graph on an odd number of vertices. Every matching in a graph has at most $r/2$ edges, so $r$ colours in a proper edge colouring could cover at most $r^2/2$ edges. ButTherefore ${\chi }^{\prime }(K_{r+1})>r$; Vizing's theorem gives ${\chi }^{\prime }(K_{r+1})=r+1$. This includes the graph triangle when $r=2$.

For odd $r\ge 3$, first construct a graph $H_r$ on $r+2$ vertices. Start with the complete graph onand delete the edges $va$, $vb$, and $c_1{c}_2,c_3{c}_4,\dots ,c_{r-2}{c}_{r-1}$. The pairing is possible because $r-1$ is even. In the initial complete graph, every vertex has vertex degree $r+1$. The distinguished vertex $v$ loses two edges and every other vertex loses exactly one, givingTake two disjoint copies of $H_r$, with distinguished vertices $v,v^{\prime }$, and add the edge $v{v}^{\prime }$. The resulting simple graph $G_r$ is an $r$-regular graph. The added edge is the only edge between the two copies; each copy has the odd number $r+2$ of vertices.

Suppose an $r$-colour proper edge colouring existed. At each vertex, the $r$ incident edges would use all $r$ colours. Thus each colour would form a perfect matching. Any perfect matching must use $v{v}^{\prime }$: without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by parity. Therefore all $r$ colour classes would have to contain the same edge $v{v}^{\prime }$, a contradiction. Hence Vizing's theorem again givesThese constructions give class two regular graphs for every $r\ge 2$. The odd-$r$ construction exhibits the bridge obstruction to regular edge colouring; $H_r$ is a connected graph because every vertex other than $a,b,v$ is adjacent to $v$, while $a,b$ are adjacent to those vertices.

Let the nonempty connected components of a graph of $G$ be $G_1,\dots ,G_t$. A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph $H$, prove $p_H(0)=0$ by mathematical induction on the number of edges. If there are no edges, then $p_H(x)=x^{|V(H)|}$ with $|V(H)|\ge 1$. Otherwise choose an edge $e$. Both $H-e$ and the simplified edge contraction $H/e$ are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction giveThus $p_{G_j}(x)=x{q}_j(x)$ for a polynomial $q_j$, andFor the empty graph, $t=0$ and $p_G(x)=1$, so the conclusion also holds. This is the chromatic polynomial product over components.

For the Erdős-Rényi model $G(n,p)$, choose the number $n$ of vertices and an edge probability $0\le p\le 1$. Visit every unordered pair of distinct vertices once and include its edge independently with probability $p$. This construction gives a simple graph with expected edge count $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and mean vertex degree $p(n-1)$.

Increasing $p$ at fixed $n$ makes the graph denser, increases typical vertex degree and local clustering coefficient, and tends to shorten graph distances and improve connectivity. Increasing $n$ at fixed $p$ also increases the mean vertex degree; to retain a sparse comparison one instead decreases $p$ approximately as $1/n$.

Its degree distribution is binomial distribution, approximately Poisson distribution in the sparse large-$n$ regime, so it is not a scale-free network. Connected realizations can have short average shortest path length, but their clustering coefficients are not elevated above the random baseline they themselves define. Thus they are not small-world networks under the high-clustering convention, although “small world” is sometimes used more loosely to mean only short distances.

The supplied adjacency matrix describes a four-vertex cycle graph, with every vertex degree equal to two. Degree-preserving edge rewiring is random, so it does not determine one unique labelled output adjacency matrix. For example, replace edges $AB$ and $CD$ by $AC$ and $BD$, retaining $AD$ and $BC$. This valid switch gives, in order $A,B,C,D$,Each row still sums to two. Under the simple graph convention, all allowed outputs have the same unlabelled four-cycle topology: there are three possible labelled four-cycles. A rejected switch or later return can also leave the original adjacency matrix.

It is not a scale-free network. Its degree distribution is concentrated entirely at degree two, with no power-law tail; degree-preserving edge rewiring cannot change that.

Use degree-preserving edge rewiring, often called a double-edge swap. Select two edges $(u,v)$ and $(x,y)$ with four distinct endpoints, then replace them by $(u,y)$ and $(x,v)$, choosing the reconnection symmetrically. Reject a proposal that would create a self-loop or an already present edge if the target is a simple graph. Each endpoint loses one edge and gains one, so every degree of a vertex, as well as the numbers of vertices and edges, is preserved exactly.

Repeat many such random proposals to generate reference networks. With symmetric proposals, retaining rejected steps as self-transitions, the uniform distribution on the reachable degree-preserving realizations is stationary. Adequate mixing must be checked; a few successful swaps do not establish an independent random sample. Degree preservation alone does not preserve connectedness, so impose and check that extra restriction if the graph distance comparison requires connected networks.

Put $M=2m$ and $a_i=\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)$. Use the configuration model: give vertex $i$ exactly $d_i$ labelled half-edges and choose a uniform perfect matching of all $M$ half-edges. There arepairings, with $(2m{)}_m$ denoting a falling factorial. Each allowed simple graph has exactly ${\prod }_i{d}_i!$ representations: at every vertex, assign its incident graph edges bijectively to its labelled half-edges. Therefore its enumeration reduces to the probability that a pairing is simple and avoids $G_0$.

Count three kinds of prescribed bad patterns. A loop pattern consists of a pair of half-edges at one vertex. A double-edge pattern consists of two half-edges at each of two distinct vertices and one of their two cross-pairings. A forbidden-edge pattern consists of one half-edge at each endpoint of an edge of $G_0$. Let their respective counts in the random pairing be $Z_L,Z_D,Z_F$. Simplicity and avoidance are equivalent to $Z=Z_L+Z_D+Z_F=0$, including exclusion of triple edges because those contain double-edge patterns.

A prescribed collection of $t$ disjoint half-edge pairs occurs with probabilityConsequently the bad-pattern expected values areHere $\lambda =({\sum }_i{a}_i)/m$ and $\mu =M^{-1}{\sum }_{ij\in E(G_0)}{d}_i{d}_j$, as in the PDF. Since $1\le d_i\le \Delta$ and $G_0$ has bounded maximum degree, $M=\Theta (n)$ and all three means are uniformly bounded. For the double-edge estimate, ${\sum }_i{a}_i^2=O(n)$, so its contribution after division by $M^2$ is $o(1)$.

We now give the moment-counting step rather than assume independence. For each fixed $h$, expand the factorial moment $\mathbb{E}(Z{)}_h$ as the sum over ordered distinct bad patterns. Collections on disjoint vertex sets have, by the displayed pairing probability, joint probabilities equal to the product probabilities times $1+O(1/n)$. Their total contribution isDeleting collections with a shared vertex changes the independent-product sum by $O(1/n)$, since all ordinary and forbidden vertex degrees are bounded.

For actual joint probabilities of overlapping patterns, incompatible uses of a half-edge give zero. Compatible collections with no shared paired edge lose at least one free vertex choice, without reducing the number of required pairs, so contribute $O(1/n)$. A shared paired edge can occur only between two double-edge patterns or between a double-edge pattern and a forbidden-edge pattern. In the first case their union requires at least three parallel paired edges: there are $O(n^2)$ endpoint choices and probability $O(n^{-3})$. In the second case the endpoint pair must be an edge of $G_0$: there are only $O(n)$ choices and at least two required pairs, giving $O(n^{-1})$. Adding further patterns in a fixed collection does not remove this deficit: a disjoint addition contributes bounded order, while an addition to an existing cluster has only bounded half-edge choices unless it supplies new free vertices, compensated by its new required pairs. Summing the finitely many overlap types for fixed $h$ therefore gives $o(1)$. Thus, with $\Lambda =\lambda /2+{\lambda }^2/4+\mu$,The Bonferroni inequalities bracket $\mathrm{Pr}(Z=0)$ by the odd and even partial sums of ${\sum }_h(-1{)}^h\mathbb{E}(Z{)}_h/h!$. The means $\Lambda$ are bounded, so the corresponding exponential-series remainders vanish uniformly as the truncation increases. Taking $n\to \infty$ and then the truncation to infinity proves the bounded-degree pairing avoidance estimate $\mathrm{Pr}(Z=0)=e^{-\Lambda }+o(1)$. This does not require $\lambda$ or $\mu$ to converge. The exponential is bounded away from zero, so the additive error is also a relative $o(1)$ error.

Multiplying by the pairing count and dividing by the representation factor givesThe factor $(2m{)}_m$ multiplies the exponential; it is not part of its exponent. The TeX aid misgroups this factor, whereas the original PDF is unambiguous. The bounded-degree proof also covers the stated additional assumption $2m-n\to \infty$.

The lower bound cannot hold at $n=3$ as printed: a simple graph on three vertices has at most three edges, so $C(3,4)=0$. We prove the intended bound for every $n\ge 4$, and hence its stated asymptotic order.

Delete leaves from a connected graph of graph excess one to obtain its nonempty 2-core. Deleting a leaf and its incident edge preserves edges minus vertices. The deleted part is a forest rooted at the core vertices: it cannot contain a cycle, which would survive deletion, and it cannot join two core vertices, since the joining path would itself survive. The 2-core remains connected. Suppress its maximal paths with degree-two internal vertices, allowing coincident endpoints for a cycle based at a branching vertex. The resulting graph kernel is a connected multigraph of minimum degree at least three, retaining loops and parallel edges, with the same excess one.

In that kernel,Thus it has either one degree-four vertex or two degree-three vertices. In the first case its two edges are loops. In the second, let $h$ be the number of edges between the two vertices and $a,b$ the loop counts. Connectivity gives $h\ge 1$, and $2a+h=2b+h=3$, leaving $h=3,a=b=0$ or $h=1,a=b=1$. This proves the bicyclic kernel classification: the two-loop bouquet graph, the three-edge Theta graph, and the two-loop dumbbell graph. Original simple cores are graph subdivisions of these kernels; loops must subdivide to cycles of length at least three, and at most one of the three theta paths can be an unsubdivided edge.

Let $b_k$ count labelled bicyclic cores on a fixed $k$-vertex set. The classification gives an absolute constant $A$ withTo see the bound concretely, order the one or two branching labels, choose one of the three kernel types, and distribute the other $k-v$ labels as ordered internal vertices of its two or three edges. There are at most $\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)=O(k^2)$ weak compositions of their lengths, and at most $k!$ ordered assignments of all labels. This overcounts orientations and edge permutations and ignores simplicity restrictions, both harmless for an upper bound.

For a lower bound, use only theta cores whose three paths each have at least one internal vertex. For $k\ge 5$, choose an ordered pair of branching vertices and an ordered list of the other $k-2$ labels, then cut that list into three nonempty ordered paths. There are $k!\left(\genfrac{}{}{0ex}{}{k-3}{2}\right)$ encodings. Every resulting simple theta core is encoded exactly $2\cdot 3!=12$ times, by swapping the branching vertices and permuting the three paths. Hence

Choose the core's vertices and attach the forest counted in part (i). The decomposition is unique, soPutting $q_{n,k}=(n{)}_k/n^k={\prod }_{j=0}^{k-1}(1-j/n)$, the two estimates on $b_k$ reduce the labelled bicyclic graph count to the sum of $k^3{q}_{n,k}$ divided by $n^2$.

For the upper bound, $\log (1-x)\le -x$ givesThe corresponding sum is $O(n^2)$. For example, divide the positive integers into blocks $j\sqrt{n}\le k<(j+1)\sqrt{n}$: the sum in block $j$ is at most a constant times $n^2(j+1{)}^3{e}^{-j^2/4}$, and the series over $j$ converges. Including the finitely small indices makes no difference. Therefore $C(n,n+1)\le c_2{n}^{n+1}$.

For the lower bound, take $n$ sufficiently large and $\sqrt{n}\le k\le 2\sqrt{n}$. Then $k\ge 8$, and $j/n\le 1/2$ throughout the product. Since $\log (1-x)\ge -2x$ on $[0,1/2]$,There are at least $\frac{1}{2}\sqrt{n}$ such integer indices, each with $k^3\ge n^{3/2}$. The lower core bound therefore givesThis proves the two-sided bounds for all sufficiently large $n$. They extend to every $n\ge 4$ by adjusting the constants over the remaining finite set: $C(n,n+1)>0$ there, since $K_4$ minus one edge is connected with five edges, and adding a pendant path supplies an example at every larger order. Consequently the correctly qualified conclusion isThe exceptional $n=3$ is a genuine defect in the printed quantifier, not a missing case of the proof.

We first establish the labelled forest count with prescribed roots. For a prescribed root set $R$ of size $k<n$, orient each tree toward its unique root. Repeatedly delete the smallest remaining nonroot leaf, recording its parent. There are $n-k$ deletions, and the final recorded parent belongs to $R$. Conversely, start with any code of length $n-k$ whose last entry lies in $R$. At each step select the smallest remaining nonroot absent from the remaining code, connect it to the code's first entry, and delete that vertex and entry. Such a vertex exists: among $s$ remaining nonroots, the remaining code has $s$ entries but at least its last entry is a root, so at most $s-1$ nonroots occur in it. Previously deleted vertices never recur in the code, so the selected parent is still present. Every edge goes from a vertex being deleted to one retained, excluding a cycle. The resulting forest has one root in each graph component, and the two constructions are inverse. Its count is thereforefor $k=n$, interpret this as one, the empty forest.

A connected simple graph with $n$ edges has exactly one cycle: a spanning tree uses $n-1$ edges, and the remaining edge creates its unique cycle. If that graph cycle has length $k$, choose its vertex set in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways and its unoriented cyclic order in $(k-1)!/2$ ways. All other edges form a forest rooted at those $k$ vertices, with exactly one cycle vertex per forest component; two roots in one attached component would create an additional cycle. Conversely every such cycle and rooted forest gives a unique unicyclic component. ThusThis is the labelled unicyclic graph count. The term $k=n$ correctly counts a cycle with no attached nonroot vertices.

Let $t$ be the maximum number of positive Euclidean distances from one of the $n$ points to the others. It suffices to prove the stronger Székely distinct-distance bound, $t\ge c{n}^{4/5}$. Here $n\ge 2$; enlarge constants to handle bounded $n$.

First prove the crossing lemma for multigraphs. In an optimal drawing of a loopless multigraph with $v$ vertices, $e$ edges and maximum parallel multiplicity $\mu$, crossings of incident edges can be removed by interchanging initial segments, so each remaining crossing involves four distinct vertices. In each parallel class choose one of its edges with probability $1/\mu$ per edge, selecting none with the remaining probability. Independently keep each vertex with probability $p$. The resulting simple graph has expected edge count $p^{2}e/\mu$, expected vertex count $pv$, and expected crossings $p^{4}X/{\mu }^2$, where $X$ is the original crossing count. Deleting one edge per crossing and using the allowed planar graph edge bound yieldsIf $e\ge 4\mu v$, take $p=4\mu v/e$ to obtainThe case $\mu =1$ is the ordinary crossing lemma.

We also need the rich line bound. Given $L$ lines, connect consecutive incidence points on each line by straight edges. This simple graph has at least $I-L$ edges, where $I$ is the total number of incidences, and at most $L^2$ crossings. The crossing lemma gives $I=O((nL{)}^{2/3}+n+L)$, proving the Szemerédi–Trotter theorem here rather than assuming it. For lines containing at least $k$ points, $I\ge kL$, and absorbing the additive $L$ term givesFor bounded $k$, counting point pairs gives the same estimate with a larger absolute constant. Grouping rich lines into occupancy ranges $2^{j}k\le s<2^{j+1}k$ and summing the resulting geometric series proves

Now form the circular-arc graph for distinct distances. Around every point draw each positive-distance circle centred there; there are at most $nt$ such circles. A circle with at least three of the original points contributes one edge between each consecutive pair around it. Discard the circles with at most two points. Since the total number of centre-to-point incidences is $n(n-1)$, the remaining loopless multigraph hasIts circular-arc drawing has $O(n^2{t}^2)$ crossings: two distinct circles have at most two intersections, and small perturbations remove tangencies and multiple crossings without changing this order.

The apparent difficulty is unbounded parallel multiplicity. The rich-bisector deletion bound controls it. Every centre supporting an arc between fixed endpoints lies on their perpendicular bisector. Distinct parallel arcs come from distinct centres, since their common endpoints determine the radius once the centre is fixed. Thus multiplicity at least $k$ makes that line contain at least $k$ of the points. For a line with $s$ centres, each of its at most $st$ circles has at most two consecutive-point arcs symmetric about that line, one at each end of its diameter along the line. The occupancy sum above therefore bounds the number of high-multiplicity arcs by

If $t\ge n^{4/5}$ there is nothing to prove. Otherwise $t\log n=o(n)$ and $t=o(n)$. Choose $k=\lceil K\sqrt{t}\rceil$ with a sufficiently large absolute constant $K$. The first deletion term is at most a small fixed fraction of $n^2$ and the second is $o(n^2)$. A remaining multigraph therefore has $e_1\ge c_1{n}^2$ edges and multiplicity at most $k$. For large $n$, $e_1\ge 4kn$, so the crossing lemma for multigraphs givesRearranging,The whole distinct-distance set contains those distances from the selected point, proving the requested bound. The circular-arc method and the stronger one-point conclusion are due to Székely.

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.