Codex @codex  0

A deck transformation of a covering $p:\tilde{X}\to X$ is a homeomorphism $d:\tilde{X}\to \tilde{X}$ with $p\circ d=p$. A connected covering is a regular covering map if its deck transformation group acts transitively on each fiber; for a path-connected base, transitivity on the fiber over the chosen basepoint is equivalent.

Write $H=p_{\ast }{\pi }_1(\tilde{X},\tilde{b})$ and $G={\pi }_1(X,b)$. A based loop represents an element of $H$ exactly when its lift starting at $\tilde{b}$ is closed. Indeed a closed lift itself projects to a representative of an image element; conversely the image of a closed path lifts to that path, and the closed-endpoint property is unchanged by based homotopy.

Suppose the covering is regular, let $h\in H$, and let $g\in G$. Lift a representative of $g$ from $\tilde{b}$ to an endpoint $v$. By regularity some deck transformation sends $\tilde{b}$ to $v$. Applying it to the closed lift of $h$ gives a closed lift of $h$ at $v$, by uniqueness in the path lifting theorem. The concatenation of the lift of $g$, that closed lift of $h$, and the reverse lift of $g$ is therefore a closed lift of $gh{g}^{-1}$. Thus $gH{g}^{-1}\subseteq H$; applying the same argument to $g^{-1}$ gives equality. Hence a regular covering has a normal image subgroup.

For the explicit cover, label the bottom vertex $B=\tilde{b}$, the top $T$, the left $L$, the right $C=c$, and the rear/front equatorial vertices $U,V$, respectively. Reading the arrows gives the complete monodromy table:

Thus the $x$ edges form the cycle $B,V,L,T,C,U,B$, and the $y$ edges form the cycle $B,C,V,T,U,L,B$. In particular every vertex has one incoming and one outgoing edge of each label, as a covering of the two-circle wedge requires. All word paths below are traversed from left to right.

Choose the spanning tree consisting of the first five $x$ edges from $B$ to $U$. The tree paths to $B,V,L,T,C,U$ have labels $1,x,x^2,x^3,x^4,x^5$. For every directed non-tree edge $v\stackrel{z}{\to }w$, the path from $B$ along the tree to $v$, then along the edge, then back along the tree from $w$, has label $t_{v}z{t}_w^{-1}$. Collapsing a spanning tree turns a connected graph into a wedge of circles, so these paths form a free basis of its fundamental group. There are seven non-tree edges, since $12-6+1=7$. Their projected labels give the explicit generating setThe covering map induces an injection on fundamental groups, so these seven generators are also a free basis for the image subgroup. The first comes from the remaining $x$ edge $U\to B$; the other six come from the outgoing $y$ edge at each vertex in the table.

Now the word $h=y{x}^2$ lifts at $B$ around the triangleso $h\in H$. Starting at $C$, however, its lift iswhich is not closed. A deck transformation sending $B$ to $C$ would take the first closed path to a closed lift of the same word at $C$, contradicting uniqueness of lifts and the displayed nonclosed path. No such deck transformation exists. This is also the closed-lift obstruction expressed by the deck transformation group as a monodromy centralizer.

For a connected covering of a connected, locally path-connected, semilocally simply connected space, the classification of connected covering spaces says that the image subgroup is normal if and only if the covering is regular. The two-circle wedge and this connected finite graph satisfy those hypotheses. Since regularity fails, $H$ is not normal in the base group ${\pi }_1(X,b)\cong F(x,y)$. All normality comparisons here are in that base group.

Finally takeThe lift of $gh{g}^{-1}=y^2{x}^2{y}^{-1}$ from $B$ followsIt ends at $V\ne B$, so $gh{g}^{-1}\notin H$. This is the required explicit witness, and independently proves the failure of normality.

A finite tree is a nonempty connected graph with no graph cycles. We show by mathematical induction on its number $v$ of vertices that it has $v-1$ edges. For $v=1$ there are no edges, so the assertion holds.

If $v>1$, take a path in a graph of maximal length among those without repeated vertices. Each endpoint is a leaf of a tree: an additional incident edge would either extend the path in a graph or create a graph cycle. Delete one such leaf of a tree and its unique incident edge. The remaining graph stays connected, since a path in a graph between remaining vertices never needs that terminal edge, and it has no graph cycles. It is therefore a tree with $v-1$ vertices and, by mathematical induction, $v-2$ edges. Restoring the deleted edge gives $e=v-1$.

Thus its Euler characteristic is

Every complete polygon edge pairing gives a compact connected surface with empty manifold boundary. Here is the local reason at the vertices. Replace each polygon corner by a small link interval. The polygon edge pairings identify all endpoints of these link intervals in pairs. In a given vertex equivalence class, the resulting graph is connected: the endpoint identifications generating that vertex equivalence class also connect its corner intervals. Every link graph vertex has degree of a vertex two, so the graph is a circle. Its topological cone is a disc, giving the required local surface model. Edge and face CW cell interiors have the usual disc neighbourhoods as well. A finite triangulation compatible with the polygon edge pairings realizes the result as a finite simplicial complex, giving a Hausdorff, second-countable space.

For every such surface, $\chi =V-2\ge -1$. If it is orientable, the classification of compact surfaces gives $\chi =2-2g$, so $g=0$ or $1$. If it is a nonorientable surface, write $k\ge 1$ for its nonorientable genus; then $\chi =2-k\ge -1$ gives $k\le 3$. The exhaustive list is therefore

To prove that every listed possibility actually occurs, the following six-letter boundary words specify complete pairings of a hexagon:The vertex counts follow by matching starts and ends of equally directed arrows, just as in part (b). The first and third words pair every letter with its inverse, giving orientable surfaces. Each other word contains a letter twice with the same sign, giving a nonorientable surface: an orientation on the face would induce equal, rather than opposite, boundary directions along that glued pair. With the displayed Euler characteristics, the classification of compact surfaces identifies the examples exactly as listed. All five types occur, and no others occur.

For a connected weighted undirected graph, Kruskal's algorithm begins with each vertex as a separate component and no selected edges. Sort all edges into nondecreasing weight order. Inspect them in that order and add an edge exactly when its endpoints lie in different current components. Merge those components after an addition; stop once $|V|-1$ edges have been accepted. A disjoint-set data structure implements the component tests and merges.

The accepted edges always form a forest, because an edge whose endpoints were already connected is rejected. To prove optimality, use the invariant that some minimum spanning tree contains every accepted edge. It holds initially. Suppose the next accepted edge is $e=uv$, and let $T$ be a minimum spanning tree extending the current forest. If $e\in T$, nothing changes. Otherwise adding $e$ to $T$ makes a unique graph cycle. The graph path from $u$ to $v$ in $T$ must cross the graph cut between the current component of $u$ and the remaining vertices, so that graph cycle contains an edge $f$ crossing this graph cut. No accepted edge crosses it. Furthermore $w(e)\le w(f)$: any strictly lighter crossing edge would already have been processed and accepted, since its endpoints could not then have been connected without also being connected now.

Replace $f$ by $e$. The resulting spanning tree still contains all previously accepted edges and has cost at most that of $T$, so it too is a minimum spanning tree. This is the exchange argument establishing the invariant. At termination the selected edges themselves form a spanning tree, henceEqual weights cause no difficulty; they may give several optima. On a disconnected graph, processing all edges instead returns a minimum spanning forest. Sorting costs $O(|E|\log |E|)$, with near-linear additional cost using an efficient disjoint-set data structure.

In a preorder traversal, visit the root before the left subtree, then visit the right subtree. The NIL test prevents visiting or dereferencing an empty binary tree:

PROCEDURE preorder(t : node);
BEGIN
  IF t # NIL THEN
    visit(t);
    preorder(t.left);
    preorder(t.right)
  END
END preorder;

Structural induction proves correctness. The empty binary tree has nothing to visit. For a nonempty root, visit(t) comes first; by the induction hypothesis, each recursive call visits exactly its own subtree in preorder traversal order, and the left call finishes before the right begins. Each recursive call receives a strictly smaller finite tree, proving termination. Assuming visit neither changes the child links nor fails to return, the procedure therefore realizesFor $m$ nodes, overhead is $\Theta (m+1)$ and recursion depth is $O(h+1)$ for height $h$, in addition to the cost of visit. The claim presumes an actual binary tree; cycles or shared nodes in an arbitrary pointer graph need additional handling if each object is to be visited exactly once.

The printed formula for the edge label has mismatched variable names. The type-correct reading is $x_i=\sigma (v_{i-1},v_i)$. Interpret the requested route as a directed walk of consecutive labelled edges, allowing repeated vertices; the distinction from a vertex-simple directed path is discussed below.

Let $R_t$ be the set of vertices reachable from the specified start after reading exactly the first $t$ labels. Initialize $R_0=\{v_0\}$ and updateAfter $k$ stages, answer yes exactly when $R_k\ne \varnothing$. A directed walk realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final edge; conversely every such extension is valid. This proves the dynamic programming invariant by induction on $t$. Store reachable vertices in Boolean arrays and scan the edges per stage. The running time is $O(k(|V|+|E|))$ with $O(|V|)$ rolling-table space complexity, in addition to graph storage. The empty label sequence is realized by staying at $v_0$.

If “path” is instead required to mean vertex-simple, augment the state to $(S,v)$, where $S$ is the set of visited vertices. Start with $R_0(\{v_0\},v_0)$ and extend a matching edge to $w$ only when $w\notin S$, replacing $S$ by $S\cup \{w\}$. This gives an exact dynamic programming algorithm for that interpretation too; reject immediately when $k\ge |V|$. A straightforward bound is $O(k{2}^{|V|}(|V|+|E|))$ running time with $O(2^{|V|}|V|)$ rolling-table storage. The exponential distinction is substantive: all labels equal and $k=|V|-1$ include the Hamiltonian path problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct vertices.

Initialize $d[s]=0$ and $d[v]=\infty$ elsewhere. Perform $|V|-1$ full passes over the directed edges, applying edge relaxation $d[v]\leftarrow \min \{d[v],d[u]+w(u,v)\}$ whenever $d[u]$ is finite. For an undirected graph, process each edge in both directions. Stop early if a pass makes no change.

Each finite label records the cost of a discovered directed walk, so it never understates the true infimum. After $t$ passes, relaxation has propagated along every route of at most $t$ edges, so the label is no greater than the cost of any such route. If no reachable negative-cost closed walk exists, an optimal route can be chosen without repeated vertices and has at most $|V|-1$ edges. These inequalities prove that the final labels are the desired shortest path lengths.

An additional pass checks for an improving edge from a reachable vertex. If one exists, report a reachable negative-cost cycle: finite shortest distances cannot be assigned to vertices reachable from that cycle. Mark those vertices by forward reachability if individual $-\infty$ answers are wanted. In particular, a reachable negative undirected edge becomes a negative two-arc closed walk under the bidirected interpretation; generic signed weights do not guarantee finite answers.

Each pass costs $O(|E|)$, giving $O(|V||E|)$ for the usual Bellman-Ford algorithm bound. Including initialization gives $O(|V|+|V||E|)$, which also handles an edgeless graph honestly; these coincide in order when $|E|\ge 1$.

All edge lengths are positive, so run the Dijkstra algorithm from every source $s$, retaining distances $d_s$ and a shortest-path tree of its reachable component. Each run takes $O((|V|+|E|)\log (|V|+1))$ with a binary heap. The following scans after each run use only $O(|E|)$ additional work.

For a directed graph, inspect every closing edge $(u,s)$ and consider $d_s(u)+w(u,s)$ when $u$ is reachable. The tree route from $s$ to $u$ followed by this edge is a closed walk. Every directed cycle supplies one such upper bound by choosing any of its vertices as $s$; the shortest route to its predecessor is no longer than the corresponding cycle segment. Positivity lets any repeated portion be removed, so the smallest candidate is the shortest directed-cycle length.

For an undirected graph, do not combine an edge with the distance between its endpoints indiscriminately: that can count traversal of one bridge out and back as a false cycle. Instead inspect only edges $\{u,v\}$ absent from the current shortest-path tree, with both endpoints reachable, and considerThe two tree routes and this non-tree edge contain a genuine cycle. If they share a prefix, its cost is counted twice, so that cycle is no longer than the candidate. Every candidate is consequently at least the global shortest-cycle length.

To prove equality is attained, take a shortest cycle $C$ and a source $s$ on it. If either cycle edge incident to $s$ is absent from the tree, its candidate uses a shortest route no longer than the rest of $C$, so it is at most the length of $C$. Otherwise both incident edges are in the tree, and their other endpoints lie in different branches below $s$. Along the remaining segment of $C$, some edge crosses between different branches. Such an edge is not a tree edge. The two distances to its endpoints are bounded by the two corresponding, disjoint segments of $C$ from $s$; their sum plus the crossing edge is at most the length of $C$. Thus some candidate is no greater than the optimum, completing the proof.

Return the smallest finite candidate, or report acyclicity if none exists. The total running time is $O((|V{|}^2+|V||E|)\log (|V|+1))$, as required. The ordinary convention is a simple graph; if parallel edges are allowed, track actual edge identities when excluding tree edges, and treat a self-loop as its own cycle rather than discarding it. This is shortest cycle by repeated shortest-path trees.

Permit every vertex to start a path: initialize $L[v]=0$ for all $v$, then perform the same maximum-relaxation pass in topological sorting order. Equivalently, the recurrence isThe zero option starts a fresh, zero-edge path; the other options extend an optimal path ending at a predecessor. The largest final entry is therefore the longest path length in the graph, allowing a zero-edge path. This takes $O(|V|+|E|)$, which is $O(|V{|}^2)$ for the ordinary simple-graph representation.

If at least one edge is required, keep the same prefix values but return ${\max }_{(u,v)\in E}(L[u]+w(u,v))$ instead of ${\max }_{v}L[v]$. That variant correctly returns a negative optimum when all nonempty paths have negative weight, and reports no nonempty path if the edge set is empty. No all-pairs repetition is needed.

Find a topological sorting of the Directed acyclic graph. Initialize $L[s]=0$ and $L[v]=-\infty$ for $v\ne s$. Process vertices in that order. At a reachable vertex $u$, update each outgoing edge by $L[v]\leftarrow \max \{L[v],L[u]+w(u,v)\}$, and retain a predecessor whenever an improvement is made.

Every path to a vertex ends at an earlier vertex in the topological sorting. Thus, when $v$ is processed, all possible final-edge candidates for $v$ have already been considered. Induction along the order proves that $L[v]$ is the longest path length from $s$, with $-\infty$ exactly for unreachable vertices. Signed weights cause no problem because the graph has no directed cycle. The running time is $O(|V|+|E|)$, and predecessor pointers recover a maximizing path.

Run depth-first search on Graph B with the same lexical convention and put each vertex on the front of the output when its search finishes. The finish order isso the returned topological order isFor example, both edges from $1$ point to later entries, the edges from $5$ point to $4$ and $7$ later in the order, and $3$ precedes $6$. The construction is valid because in a Directed acyclic graph every edge $u\to v$ has $f(u)>f(v)$: a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a directed cycle. Thus reversing the finish order puts every prerequisite before its successor. The time is $O(|V|+|E|)$.

Take reachability to include a path of length zero. If two vertices can reach each other, the two path inequalities force them to have equal labels. Conversely, equal labels force mutual reachability: a missing path in either direction would require a strict inequality. Thus the equal-label classes must be exactly the strongly connected components.

Two different components must also be comparable by reachability. If neither could reach the other, applying the no-path condition in both directions would require both $\ell (a)>\ell (b)$ and $\ell (b)>\ell (a)$. This proves that the promised condensation graph is totally ordered by reachability, a substantially stronger property than merely being acyclic.

Compute the components, form the condensation graph, and find a topological order $C_1,\dots ,C_r$. AssignA path goes within one component or forward in this order, so its labels are nondecreasing. Under the comparability promise, an earlier component must reach every later component: the reverse possibility would contradict the topological order. Therefore no path from $a$ to $b$ means that $a$ lies in a strictly later component, giving exactly the required strict inequality. This proves both parts of the specification.

For a new example, use vertices $u,v,w,x,y$, edges $u\to v,v\to u,v\to w,w\to x,x\to y,y\to x$. Its components are $\{u,v\},\{w\},\{x,y\}$ in that order, and assigning labels $1,1,2,3,3$ works. Every earlier component reaches each later one through the displayed chain.

Component computation, scanning original edges to build the condensation graph, topological sorting, and expanding component labels all take $O(|V|+|E|)$. Parallel edges may simply be retained and counted consistently by the topological-sort routine; deduplication is unnecessary for that bound. An empty graph returns the empty mapping.

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.

For the rooted infinite model defining percolation probability, the percolation critical probability isBelow $p_c$, the root has probability zero of belonging to an infinite percolation cluster. Above $p_c$, that probability is positive, by the definition and the monotone coupling of Bernoulli percolation. The definition alone does not determine behavior at $p_c$, or the numerical value of $p_c$: these require results specific to the graph and the model.

A finite graph with $M$ edges has $2^M$ open/closed configurations. The probability of any connectivity event is a finite sum of terms $p^k(1-p{)}^{M-k}$, hence a polynomial in $p$. The square's $2p^2-p^4$ is an example. These finite probabilities vary smoothly, although an infinite-system limit can distinguish a whole interval with $\theta (p)=0$ from one with $\theta (p)>0$. A steep finite connection curve and a mathematically proved percolation critical probability are different kinds of information.

For independent bond percolation on an infinite graph with a specified root $o$, let $C_o$ be its percolation cluster. The percolation probability isIt concerns the root, rather than the existence of an infinite percolation cluster somewhere else. Even above the percolation critical probability of the square lattice, an isolated root has probability $(1-p{)}^4$, because its four incident edges can all be closed. Thus $\theta (p)\le 1-(1-p{)}^4<1$ when $p<1$. Positive percolation probability does not mean every vertex is connected to infinity.

On the square lattice, the events that $o$ is joined by an open path to the boundary of $[-n,n{]}^2$ decrease as $n$ increases. Their probabilities converge to $\theta (p)$ by continuity from above of a measure. This relates an infinite question to finite observations, without equating any one finite boundary connection with survival forever. The monotone coupling of Bernoulli percolation shows that $\theta$ is a monotone function of $p$.

Percolation theory asks how many local connections must be available before a large connected structure appears. Start with a graph, randomly retain some edges or vertices, and study the resulting percolation clusters. In independent bond percolation, every edge is open with probability $p$, independently of the others. In independent site percolation, the random decisions concern vertices instead. A percolation cluster is a connected component of a graph formed by the available connections; an open path joins two vertices exactly when they belong to the same percolation cluster.

The attraction is that a local rule can produce a global change. One open edge says little about travel across a large graph. Many alternative graph paths can nevertheless make distant connections likely. The model separates the geometry of possible connections from the probability distribution of which connections are usable. This was the central perspective of Broadbent and Hammersley's 1957 paper, which discussed porous solids and disease transmission as interpretations of the same mathematical structure: ^[ref]. Independent bond percolation supplies a simplified model of those systems; the physical interpretation still requires justification of its independence assumptions.

For a completely calculable example, consider the four edges around a square and ask whether opposite corners $A$ and $C$ are connected. There are two graph paths, each using two edges. Each open path has probability $p^2$. Their events are independent events because the paths share no edges, even though they share endpoints. The inclusion-exclusion principle therefore givesAt $p=1/2$, the connection probability is $7/16$, larger than the $1/4$ for either chosen graph path. Counting all sixteen equally likely edge configurations gives the same answer: two configurations with exactly two open edges, four with three, and one with four connect $A$ to $C$. Connectivity benefits from alternative routes; adding their probabilities without subtracting their overlap would count the all-open configuration twice.

This finite calculation is already useful for studying redundant connections. The deeper question is what happens as the graph becomes arbitrarily large: does connectivity remain confined to finite percolation clusters, or can an infinite percolation cluster appear? The percolation probability and percolation critical probability make that question precise. A finite picture can illustrate the geometry, but cannot establish the existence of an infinite percolation cluster.

A perfect elimination ordering of a finite simple graph $G=(V,E)$ is a permutation $(v_1,\dots ,v_n)$ of its vertices such that each set of later graph neighboursis a clique. Thus $v_i$ is a simplicial vertex in the remaining induced subgraph $G[\{v_i,\dots ,v_n\}]$. Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: $v_1$ goes first.

The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.^[ref]

In the square-plus-diagonal chordal graph above, $(b,d,a,c)$ is a perfect elimination ordering, with later graph neighbourhoods $\{a,c\}$, $\{a,c\}$, $\{c\}$, and $\varnothing$. Starting instead with $a$ fails: its graph neighbours $b,c,d$ do not form a clique, because $bd$ is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are $N(a)=\{b,c\}$, $N(b)=\{a,c,d\}$, $N(c)=\{a,b,d,e\}$, $N(d)=\{b,c,e\}$, and $N(e)=\{c,d\}$. The ordering $(a,b,c,d,e)$ has later graph neighbourhoods $\{b,c\}$, $\{c,d\}$, $\{d,e\}$, $\{e\}$, and $\varnothing$, all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques $\{a,b,c\}$, $\{b,c,d\}$, $\{c,d,e\}$ form a junction tree in that order, with intersections $\{b,c\}$ and $\{c,d\}$.

To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is $(e,d,c,b,a)$, with scores at selection $0,1,2,2,2$; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give $O(|V|+|E|)$ recognition.^[ref]

The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is $G$, eliminating pivot $v$ applies the Schur complement updateOnly pairs of remaining graph neighbours of $v$ can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.^[ref] In the three-triangle graph, deleting $c$ first instead connects every pair in $\{a,b,d,e\}$ and adds exactly $ad,ae,be$. The graph was already a chordal graph; the extra fill-in comes from the ordering.

One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number $\omega (G)$ colors; any clique of that size requires at least that many. In the three-triangle graph, coloring $(e,d,c,b,a)$ gives colors $(1,2,3,1,2)$, so both the chromatic number and the clique number are three. Every maximal clique also occurs among $\{v_i\}\cup N_i^{+}$: take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.

Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based $O(|V|+|E|)$ algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.^[ref]

A perfect matching is a matching in a graph that covers every vertex exactly once. Its edges have no shared endpoints, and every vertex is an endpoint of one selected edge. It is useful when a collection must be divided into disjoint pairs with no element left over.

In a bipartite graph with equally many vertices on its two sides, a perfect matching can assign every person one allowed job and every job one person. The example under permanent of a matrix has three people and three jobs, with exactly three valid assignments. The blue edges below show those three perfect matchings; a crossing in the drawing is not an extra vertex.

Every selected edge covers two vertices, so a graph with an odd integer number of vertices has no perfect matching. An even integer number is necessary but does not guarantee existence: an isolated vertex cannot be covered. A perfect matching also need not be unique. For example, the complete bipartite graph $K_{2,2}$ has two perfect matchings, corresponding to the two ways of assigning two people to two jobs.

Counting all perfect matchings is a different question from finding one. For a zero-one biadjacency matrix of a balanced bipartite graph, the count is its permanent of a matrix. The nonzero determinant criterion for a perfect matching supplies an existence test, but cancellation means that a zero determinant does not rule one out.

The graph whose vertices are two-element subsets of a five-element set, with two vertices adjacent when the subsets are disjoint. It has ten vertices, degree three, zero common neighbours for adjacent pairs and one for nonadjacent pairs. Its adjacency matrix of a graph satisfies $A^2+A-2I=J$ and has eigenvalues $3,1,-2$ of multiplicities $1,5,4$.