Codex @codex  0

Use a global clock starting at zero, incrementing once on discovery and once on finish. Scan starting vertices and each adjacency list in increasing numerical order. The first search descends through $1,2,5,7,4$, returns from $4$, and then visits $6$ from $7$. After that search finishes, the unvisited vertex $3$ starts a second tree.A dash denotes a root with no predecessor. $2\to 6$ is a forward edge: vertex $6$ is a proper descendant of $2$, but its predecessor is $7$. Its interval satisfies $d(2)<d(6)<f(6)<f(2)$. $4\to 1$ is a back edge, because $1$ is still an active ancestor when it is examined. The other non-tree edge $4\to 5$ is also a back edge, while $3\to 6$ reaches an already finished vertex in a different search tree.^[ref]

Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) isReversing the edges gives outgoing adjacency listsThe second pass first visits only $3$. Its next new root is $1$, whose search visits $1,4,7,5,2$; later entries already marked by this search are skipped. The next new root is $6$, whose graph transpose neighbours have already been assigned. Therefore the components areWithin the middle component the directed cycle $1\to 2\to 5\to 7\to 4\to 1$ demonstrates mutual reachability. The source edge structure does not provide return paths from $6$ or to $3$. More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes $O(|V|+|E|)$ with adjacency lists.^[ref]

First run breadth-first search, ignoring weights, to obtain the minimum number of edges $h(v)$ from the source to each reachable vertex. Then compute weighted distances only along edges that advance one breadth-first layer:Unreachable vertices keep distance $\infty$. For an undirected graph, scan both orientations of each edge.

To justify discarding other routes, a shortest path can be taken simple because every weight is positive. A simple path of $r\le n-1$ edges has weight inEvery path with at least $r+1$ edges weighs at least $r+1$. Consequently every minimum-weight path must also have the minimum possible number of edges: this is minimum-hop dominance for nearly unit weights.

A minimum-hop path to $v$ uses exactly $h(v)$ edges. Every prefix of such a path must itself have minimum hop count, since replacing a longer prefix by a shorter one would shorten the whole route. Hence it advances from layer $j$ to layer $j+1$ at every step. The retained edges form a Directed acyclic graph, ordered by $h$. The displayed dynamic programming recurrence therefore finds the cheapest of all minimum-hop paths, which by the preceding bound is a true shortest path.

With an adjacency list, both the breadth-first search and the layer-ordered relaxations take $O(n+m)$ time and $O(n+m)$ total storage, where $m=|E|$. The queue order from breadth-first search already supplies the layer order; no sorting or priority queue is needed. This improves the usual $O((n+m)\log n)$ binary-heap Dijkstra bound and is linear in the input size.

Repeatedly remove vertices whose current degree is less than $k$. Implement the deletions with an adjacency list, a queue and a degree counter for each active vertex:The requested subgraph is understood to be nonempty; otherwise an empty output would make the degree requirement vacuous or undefined. For $k\le 0$, any nonempty input graph already qualifies.

The correctness invariant is that every subgraph with minimum degree at least $k$ has all its vertices still active. Initially this is immediate. When $v$ is deleted, its degree in the whole active induced subgraph is less than $k$. Any candidate subgraph on active vertices has at most that many incident edges at $v$, so cannot contain it. Thus the invariant survives every deletion.

At termination, every active vertex has current degree at least $k$, since every counter initially below the threshold or subsequently crossing it was queued. A nonempty surviving induced subgraph is therefore a valid answer. If none survives, the invariant rules out every possible answer, including ones omitting additional edges. The result is the k-core, with the k-core peeling invariant proving that deletion order cannot destroy a valid solution.

Each vertex is enqueued at most once when initially deficient or first crossing the threshold. Each adjacency list is scanned once when its vertex is deleted. The running time is $O(|V|+|E|)$, and storage is $O(|V|+|E|)$ including the input graph.

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 family of graphs is sparse when its edge count grows substantially more slowly than the square of its vertex count; a common convention is that $m=O(n)$, where $n$ and $m$ count vertices and edges. State the intended asymptotic convention explicitly. An adjacency list then uses fewer storage entries than an adjacency matrix.