Graph theory

A path-cycle matching in a finite simple graph is a collection of mutually vertex-disjoint paths and cycles in a graph. Its used edges form a subgraph with every degree of a vertex at most two. Conversely, every finite connected component of a graph with maximum degree at most two is a graph path, a cycle in a graph, or an isolated vertex; following successive edges proves this classification. Discarding unused isolated vertices therefore converts any such subgraph into a path-cycle matching without changing its edge count. On a bipartite graph, maximizing the used edges is exactly bipartite b-matching with every

b_{v} = 2

Tree decomposition ( $(T, (B_{t})_{t \in V (T)})$ )

A tree of bags of graph vertices such that every vertex occurs in a bag, both endpoints of every graph edge occur together in a bag, and the bags containing any fixed vertex form a connected connected subgraph of a tree. Its width is

max_{t} ∣ B_{t} ∣ - 1

. The connected-occurrence condition lets subproblems agree on shared variables while solving a constraint satisfaction problem; an arbitrary cover of edges by small bags is insufficient.

Treewidth ( $tw (G) = min_{T} (max_{B \in T} ∣ B ∣ - 1)$ )

The minimum width of a tree decomposition. A tree has width at most one, while a clique of

k

vertices forces width at least

k - 1

. Every pair of vertices in the clique shares a bag; their connected bag connected subgraphs of a tree have a common intersection by the Helly property of connected connected subgraphs of a tree, placing the whole clique in one bag. Small treewidth is useful for dynamic programming on finite-domain constraint satisfaction problems.

K-core peeling invariant

During repeated deletion of vertices of current degree below

k

, every subgraph of minimum degree at least

k

is contained in the active induced subgraph. If an active vertex has degree below

k

, its degree in any subgraph of the active graph is no greater, so no candidate can contain it. This proves the invariant inductively. A queue of threshold crossings and adjacency lists implements peeling in

O (∣ V ∣ + ∣ E ∣)

time.

K-core ( $C_{k} (G)$ )

The unique maximal induced subgraph with minimum vertex degree at least

k

, possibly empty. It is found by repeatedly deleting vertices of degree below

k

. The k-core peeling invariant proves that every subgraph satisfying that degree bound survives inside the result; in particular the final vertex set does not depend on deletion order.

Dominating set ( $V = D \cup ⋃_{v \in D} N (v)$ )

A dominating set

D

of a graph is a vertex subset such that every unselected vertex has a neighbour in

D

. Equivalently every vertex lies in

D

or is adjacent to an element of

D

. This condition differs from vertex cover, which requires every edge to have an endpoint in the selected set.

Edge cover ( $F \subseteq E, ⋃_{e \in F} e = V$ )

An edge cover of a finite graph is a subset of its edges incident to every vertex. It exists if and only if there is no isolated vertex, with the empty graph covered by the empty set. A minimum-cardinality edge cover uses as few edges as possible; a minimum-weight edge cover minimizes their total weight. These objectives are related to maximum cardinality matching and maximum-weight matching, respectively, by the edge cover and matching identity and minimum-weight edge cover by matching savings.

Minimum-weight edge cover

An edge cover minimizing the sum of selected edge weights. For nonnegative weights and no isolated vertex, it is computable in polynomial time by the minimum-weight edge cover by matching savings construction. It need not have minimum cardinality.

Network robustness

Persistence of a specified network property under a specified class of perturbations. Robustness of connectivity and robustness of dynamical function are different questions.

Network redundancy

Alternative routes or components can preserve function after failure, provided they do not share the same relevant failure mode.

Network resilience

Maintenance or recovery of specified network performance after a disturbance, including its transient response and recovery time.

Cascading failure

A failure changes loads or dependencies so that further components fail. Connectivity of the surviving graph alone does not determine whether a cascade occurs.

Network motif

A small interaction pattern occurring unusually often relative to a specified network null model. A circuit's wiring and proposed dynamical function should be distinguished from the statistical evidence that its pattern is enriched in a network.

Réka Albert

Work by Réka Albert

 Tagged

Albert-László Barabási

Work by Albert-László Barabási

 Tagged

Emergence of scaling in random networks by Albert-László Barabási and Réka Albert

Duncan J. Watts

Work by Duncan J. Watts

 Tagged

Collective dynamics of small-world networks by Duncan J. Watts and Steven H. Strogatz

Community detection

Community detection partitions a network into groups according to a specified structural criterion, often excess internal connectivity. The output depends on the objective, so a partition inferred from topology need not by itself establish distinct biological functions.

Network null model

A network null model specifies the reference network ensemble or expected connectivity against which a pattern is measured. For standard network modularity, expected edge weight is

k_{i} k_{j} / (2 m)

. The reference is part of the scientific model: choosing a different reference can change what counts as excess structure.

Network modularity ( $Q = (2 m)^{- 1} \sum_{ij} (A_{ij} - k_{i} k_{j} / (2 m)) 1 {c_{i} = c_{j}}$ )

Network modularity measures excess within-community edge weight relative to a network null model based on degrees of vertices. For an undirected unweighted graph, its standard form is

Q = (2 m)^{- 1} \sum_{ij} (A_{ij} - k_{i} k_{j} / (2 m)) 1 {c_{i} = c_{j}}

. A single community containing every vertex has

Q = 0

; a partition with more internal connectivity than expected can have positive

Q

Louvain method

The Louvain method is a greedy multilevel community detection algorithm maximizing network modularity. It alternates positive-gain single-vertex moves with contraction of communities into weighted vertices. Different vertex orders can produce different local optima; a result is not a certificate of globally maximum modularity.^[ref]

Eigenvector centrality ( $A v = λ_{m a x} v$ )

 2  0

Eigenvector centrality assigns nonnegative vertex scores proportional to the sum of neighbouring scores:

v_{i} = λ_{m a x}^{- 1} \sum_{j} A_{ij} v_{j}

. It uses a nonnegative eigenvector of the adjacency matrix for its largest positive eigenvalue. State the normalization, such as Euclidean norm one. For a three-leaf star graph, hub and leaf scores have ratio

3

Degree-preserving edge rewiring

Degree-preserving edge rewiring replaces two edges

(u, v)

and

(x, y)

(u, y)

and

(x, v)

, preserving every endpoint's degree of a vertex. On simple graphs, reject proposed self-loops and duplicate edges. Symmetric random proposals with rejected moves retained preserve a uniform distribution on the reachable realizations; adequate mixing remains a separate requirement. Connectivity can change unless explicitly constrained.

Scale-free network ( $P (k) \propto k^{- γ}$ )

A scale-free network has a degree distribution with an approximately power-law tail over a meaningful range. Evidence requires degrees from enough vertices to assess that range and compare alternative tail models. Large clustering coefficients or short graph distances alone do not establish this property.

Degree distribution ( $P (k)$ )

A degree distribution assigns the fraction or probability of vertices having each degree of a vertex. For an observed network,

P (k) = # {i : k_{i} = k} / n

. Preserving every labelled degree preserves this distribution, but preserving only its mean does not.

Small-worldness ( $σ = (C / C_{rand}) / (L / L_{rand})$ )

Small-worldness compares a network's clustering and average shortest-path length to reference values through

σ = (C / C_{rand}) / (L / L_{rand})

. The common

σ > 1

classification is a ratio-based convention rather than a significance test; random-reference variability must be assessed separately.^[ref]

Small-world network

A small-world network combines elevated local clustering coefficients with mean graph distance comparable to a chosen reference ensemble of random graphs. Both the reference ensemble and the clustering convention must be specified. A network can have these properties without having a power-law degree distribution.

Clustering coefficient ( $C_{i} = 2 e_{i} / [k_{i} (k_{i} - 1)]$ )

For a vertex with

k_{i} \geq 2

neighbours in a simple graph, its local clustering coefficient is

C_{i} = e_{i} / (2 k _{i})

, where

e_{i}

counts edges among those neighbours. It is the fraction of possible neighbour-neighbour edges that are present. A common network summary averages these local coefficients, setting them to zero for degrees below two; this differs from weighting by the number of neighbour pairs.

Spanning forest

An acyclic spanning subgraph containing a spanning tree of each connected component of the original graph. For a graph with

n

vertices and

c

components, a spanning forest has

n - c

edges.

Circle graph

The intersection graph of chords of a circle: each chord is a vertex, and two vertices are adjacent when their chords cross. Two chords with distinct endpoints cross exactly when their endpoints alternate around the circle.

Permutation graph

The intersection graph of the segments in a permutation diagram. Two segments cross exactly when their endpoint orders disagree. A set of mutually noncrossing segments corresponds to a monotone subsequence of the endpoint permutation.

Permutation diagram

A diagram of straight segments joining two parallel lines, with distinct endpoints on each line. Ordering the endpoints along the two lines encodes a permutation; crossing segments define the associated permutation graph.

Graph bandwidth

Interval graph

Pathwidth

Chip-firing game

A discrete process in which a vertex holding at least its degree in chips may send one chip along each incident edge. On the infinite line, a firing removes two chips from a site and gives one to each neighbor. When stabilization exists, commuting local firings explain why their order does not change the final stable configuration.

Abelian sandpile model

De Bruijn graph

For an alphabet of size

q

, the order-

n

directed graph has words of length

n - 1

as vertices and words of length

n

as edges. An edge goes from its prefix of length

n - 1

to its suffix of that length. An Eulerian cycle therefore lists every length-

n

word once as a cyclic window, producing a De Bruijn sequence.

Geometric spanner ( $d_{G} (u, v) \leq t ∥ u - v ∥$ )

A geometric spanner is a weighted graph on points in Euclidean space, with edge weights equal to their Euclidean distances, in which every pair has a graph path of length at most

t

times its direct distance. Its stretch factor is the largest ratio

d_{G} (u, v) /∥ u - v ∥

, where

d_{G}

is shortest-path distance. A square's four perimeter edges, without diagonals, give stretch factor

2

: adjacent points have ratio one, and diagonal pairs have route length

2

instead of

2

. The aim is to retain short routes with fewer edges than a complete graph. ^[ref].

Graph excess ( $exc (G) = ∣ E (G) ∣ - ∣ V (G) ∣$ )

Here excess means edges minus vertices. For a connected graph it is one less than the number of independent cycles. Deleting a leaf and its incident edge, or suppressing a degree-two vertex, preserves excess. This convention differs by one from the cyclomatic number for connected graphs.

Bicyclic graph ( $∣ E ∣ = ∣ V ∣ + 1$ )

A connected bicyclic graph has two independent cycles, equivalently excess one. Its 2-core has the same excess and every removed vertex lies in a tree attached to the core. The graph kernel captures the finite collection of possible branching structures.

Labelled bicyclic graph count ( $C (n, n + 1) = Θ (n^{n + 1}) (n \geq 4)$ )

b_{k}

counts labelled bicyclic cores on

k

vertices, the bicyclic kernel classification gives

b_{k} \leq A k! k^{2}

. Three internally nonempty paths between two branching vertices give

b_{k} \geq k! (2 k - 3) /12

for

k \geq 5

. Attach a forest with those core vertices as roots to obtain

C (n, n + 1) = \sum_{k} (k n) b_{k} k n^{n - k - 1}

. After division by

n^{n + 1}

the relevant sum is

n^{- 2} \sum_{k} k^{3} (n)_{k} / n^{k}

. Its upper bound follows from

(n)_{k} / n^{k} \leq e^{- k (k - 1) / (2 n)}

; its lower bound uses

n \leq k \leq 2 n

, where this product stays bounded below. The sum is bounded above and below by positive constants. The restriction

n \geq 4

is necessary:

C (3, 4) = 0

Bicyclic kernel classification

The graph kernel of a bicyclic graph satisfies

\sum_{v} (de g v - 2) = 2

, with all degrees at least three. It therefore has either one degree-four vertex carrying two loops, a bouquet graph, or two degree-three vertices. In the latter case connectivity and degree counting give either three parallel edges, the three-edge Theta graph, or one edge between the vertices and one loop at each, a dumbbell graph. All bicyclic cores are subdivisions of these three kernels, subject to simplicity restrictions on loop lengths and parallel paths.

2-core of a graph ( $C_{2} (G)$ )

The 2-core is what remains of a finite simple graph after repeatedly removing every vertex with fewer than two surviving graph neighbours. It strips away dangling trees while keeping the part that can support itself under this local rule. Precisely, for an undirected graph

G = (V, E)

, its 2-core is the unique maximum by set inclusion induced subgraph

G [S]

such that

de g_{G [S]} (v) \geq 2 for every v \in S .

The empty vertex set is allowed: the condition is then vacuous, without needing to define the minimum degree of the empty graph. "Maximum by inclusion" means that

S

contains every other vertex set satisfying the condition. It is stronger than merely saying that one chosen set cannot be enlarged: the 2-core simultaneously contains all possible qualifying induced subgraphs. In this particular family, every inclusion-maximal qualifying set does equal that unique maximum; the union argument in why the 2-core is unique explains why. ^[ref]

For a complete worked example, let

ab

denote the edge

{a, b}

and take

V = {a, b, c, d, e, f, g, z}, E = {ab, b c, c a, c d, d e, e f, d g} .

The triangle in a graph

ab c

has a branching tail attached at

c

, and

z

is an isolated vertex. In alphabetical order the initial degrees of vertices are

(2, 2, 3, 3, 2, 1, 1, 0)

. Deleting

f

turns

e

into a leaf of a graph; deleting

g

leaves

d

with degree of a vertex two; deleting

z

changes no other degree of a vertex. Now delete

e

, which makes

d

a leaf of a graph, and finally delete

d

. Exactly the three edges of

ab c

remain:

C_{2} (G) = G [{a, b, c}]

A forest has empty 2-core: every nonempty finite forest has an isolated vertex or a leaf of a graph, so deletion cannot stop at a nonempty remainder. In particular, an isolated edge, an isolated vertex, a path graph, and the empty graph all have empty 2-core. Every cycle graph is its own 2-core. Two disjoint triangles in a graph also form their own 2-core, so a 2-core need not be a connected graph; attaching a tree to either triangle changes neither surviving triangle.

Leaf pruning for the 2-core

Use adjacency lists and a FIFO queue to implement the deletion rule in time complexity

O (∣ V ∣ + ∣ E ∣)

. Compute each initial degree of a vertex once, mark every vertex alive, and put all vertices of degree of a vertex zero or one in the FIFO queue. Each vertex is inserted at most once. Repeatedly remove the front vertex

v

, mark it dead, and traverse its original adjacency list. For each still-alive graph neighbour

u

, decrease the stored degree of a vertex of

u

by one; if it has just become one, append

u

. A vertex already queued can drop from one to zero before its turn, but it stays queued and requires no second insertion. Stop when the FIFO queue is empty; the alive vertices induce

C_{2} (G)

For the displayed example, initially enqueue

(f, g, z)

in that order. The successive FIFO queues, after each deletion and all its updates, are

(f, g, z) - f (g, z, e) - g (z, e) - z (e) - e (d) - d () .

This explains the delayed deletion of

d

: its initial degree of a vertex was three, but the relevant degree of a vertex is always its current one in the surviving induced subgraph. Removing only the original vertices of degree of a vertex one would give the wrong answer.

Initialization inspects every vertex and every adjacency list entry once. During deletion each original adjacency list is traversed at most once, so at most

2∣ E ∣

entries are inspected in an undirected graph. All insertions, removals and stored-degree updates cost constant time each. Thus total time complexity is

O (∣ V ∣ + ∣ E ∣)

and additional storage, beyond the adjacency lists, is

O (∣ V ∣)

. The cost includes isolated vertices; repeatedly rescanning the whole surviving graph after each deletion would lose this bound. The single-threshold FIFO queue method is enough for the 2-core; the full k-core of a graph decomposition computes all thresholds.

Why the 2-core is unique

Suppose

T

is any vertex set whose induced subgraph has every degree of a vertex at least two. No vertex of

T

can be the first one deleted from

T

: before such a deletion it still has its two graph neighbours within

T

, contradicting eligibility for deletion. Consequently every qualifying

T

survives every legal deletion sequence. Once deletion stops, its remainder

R

itself qualifies, because every surviving vertex has at least two surviving graph neighbours. Therefore

T \subseteq R

for every qualifying

T

G [R]

is the unique maximum and the final remainder is independent of deletion order. The intermediate FIFO queues and deletion orders can differ.

There is also a direct existence argument. If

A

and

B

qualify, then

A \cup B

qualifies: each vertex retains at least the two graph neighbours it already had in

A

or in

B

. Taking the union of all qualifying vertex sets produces the maximum. This rules out a collection of competing, incomparable inclusion-maximal answers. It also explains why restricting the search to connected subgraphs would change the question.

Bridges and connectivity in the 2-core

A 2-core can contain bridges in a graph, and even vertices that lie on no cycle in a graph. Consider the dumbbell graph, also called a barbell in this example, made of two disjoint triangles in a graph joined by a graph path with two internal vertices:

V = {a, b, c, x, y, d, e, f}, E = {ab, b c, c a, c x, x y, y d, d e, e f, fd} .

Here

c, d

have degree of a vertex three, and every other vertex has degree of a vertex two. No deletion is possible, so the whole graph is its 2-core. Yet

c x, x y, y d

are bridges in a graph: deleting any one separates the two triangles. None belongs to a cycle in a graph, and

x, y

belong to no cycle in a graph either. Keeping only edges on graph cycles would incorrectly discard the entire joining graph path.

Figure 1.
Every vertex of this dumbbell graph survives in the 2-core, including the joining graph path whose three edges are bridges in a graph
. **Details**.

Every cycle in a graph does survive pruning, because each of its vertices keeps its two cycle graph neighbours. The barbell shows that the converse fails: the 2-core can be larger than the union of all graph cycles. Its condition is local minimum degree, not protection against a single connection failing.

A biconnected component is a different object: a maximal connected subgraph with no cut vertex of its own. Under the block convention used here, the barbell has five biconnected components: its two triangles and its three individual joining edges, each with its endpoints. Its cut vertices are

c, x, y, d

. A 2-connected component with at least three vertices must remain connected after any single vertex is deleted; the whole barbell fails that test. An informal phrase such as "biconnected core" therefore needs its own definition and must not be substituted for 2-core. Even an isolated edge is a block under this convention, although its 2-core is empty.

The usefulness of the 2-core is this precise separation of local persistence from global robustness. In a connected graph with nonempty 2-core, the deleted vertices form a forest, with each of its connected components of a graph attached by exactly one edge to the 2-core. Otherwise a deleted graph cycle, or a graph path joining two surviving attachment points, would itself have survived. Stripping these attached trees exposes a smaller structure for studying graph cycles, graph excess and the graph kernel, while preserving the joining bridges in a graph that organize that structure.

Graph kernel ( $K (G)$ )

For a connected graph whose 2-core contains a vertex of degree of a vertex at least three, suppress each maximal graph path with degree-two internal vertices to a single edge, allowing its two endpoints to coincide. Here suppression is the reverse of graph subdivision. The resulting multigraph, retaining self-loops and parallel edges, is its graph kernel. Each suppressed internal vertex removes one vertex and one edge, preserving graph excess; counting a self-loop twice toward degree of a vertex, every remaining vertex has degree of a vertex at least three. A purely cyclic 2-core is a separate unicyclic case: it has no branching vertex to anchor this construction.

For the barbell in bridges and connectivity in the 2-core, the graph kernel has two vertices

c, d

, one self-loop at each, and a single joining edge

c d

. Suppressing

x, y

contracts the joining graph path to that bridge in a graph; suppressing the two other vertices on each triangle turns the triangle into a self-loop. The graph excess stays

9 - 8 = 3 - 2 = 1

. Thus forming a graph kernel compresses degree-two chains rather than deleting everything outside graph cycles.

k-core of a graph ( $C_{k} (G)$ )

For a nonnegative integer

k

, the k-core of a graph is the unique maximum by set inclusion induced subgraph in which every degree of a vertex is at least

k

, allowing the empty graph. Repeatedly delete vertices whose current degree of a vertex is less than

k

. These induced subgraphs are nested:

C_{k + 1} (G) \subseteq C_{k} (G)

; the case

k = 2

is the 2-core. In their 2003 preprint, Vladimir Batagelj and Matjaž Zaveršnik give an algorithm for the entire core decomposition, using degree buckets and constant-time position updates. Their general bound is

O (∣ V ∣ + ∣ E ∣)

; the title's

O (m)

form applies to connected graphs with at least two vertices, where

m = ∣ E ∣ \geq ∣ V ∣ - 1

. ^[ref]

Chordal graph

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph

C_{4}

, take vertex set

{a, b, c, d}

and set of edges

{ab, b c, c d, d a}

, where

ab

abbreviates

{a, b}

. Its graph neighbourhoods are

N (a) = N (c) = {b, d}

and

N (b) = N (d) = {a, c}

. The square is an induced cycle, so

C_{4}

is not a chordal graph. Add the single edge

a c

: now

N (a) = {b, c, d}

N (b) = {a, c}

N (c) = {a, b, d}

, and

N (d) = {a, c}

. The only possible four-vertex graph cycle has chord

a c

, so this new graph is a chordal graph. Its maximal cliques are exactly

{a, b, c}

and

{a, c, d}

Figure 1.
An induced cycle loses its obstruction when one diagonal is added; the resulting maximal cliques form a junction tree
. **Details**.

Connect these two maximal cliques by a single edge labelled with their intersection

{a, c}

. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here

a, c

occur in both nodes, while

b, d

each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph

K_{5}

is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound

∣ E ∣ \leq 3∣ V ∣ - 6 = 9

. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables

x_{a}, x_{b}, x_{c}, x_{d}

with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can have

p (x_{a}, x_{b}, x_{c}, x_{d}) = Z^{- 1} ψ_{ab c} (x_{a}, x_{b}, x_{c}) ψ_{a c d} (x_{a}, x_{c}, x_{d}),

where the two nonnegative clique potentials have a positive normalizing constant

Z

. Eliminating

x_{b}

produces the two-variable junction-tree sum-product message

m (x_{a}, x_{c}) = \sum_{x_{b}} ψ_{ab c} (x_{a}, x_{b}, x_{c}), Z = \sum_{x_{a}, x_{c}, x_{d}} m (x_{a}, x_{c}) ψ_{a c d} (x_{a}, x_{c}, x_{d}) .

The shared clique

{a, c}

carries everything needed from the eliminated side. For

q

possible states per random variable, this example uses two sums over

q^{3}

configurations after reusing the message, rather than directly summing over

q^{4}

configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

Triangulation of an undirected graph

Triangulation adds fill edges to an undirected graph to make it a chordal graph. Given an elimination ordering, join all remaining neighbors of each removed vertex. The completed graph has that perfect elimination ordering. Fill edges can enlarge the cliques used for exact probabilistic graphical model inference, without changing the original probability factors; they do not assert new biological relationships.

Perfect elimination ordering

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 neighbours

N_{i}^{+} = {v_{j} : j > i, {v_{i}, v_{j}} \in E}

is 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

\emptyset

. Starting instead with

a

fails: its graph neighbours

b, c, d

do not form a clique, because

b d

is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, using

V = {a, b, c, d, e}, E = {ab, a c, b c, b d, c d, ce, d e} .

The 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

\emptyset

, 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}

Figure 1.
A perfect elimination ordering removes three overlapping triangles without fill-in; choosing the central vertex first adds three edges
. **Details**.

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 update

a_{u w} ⟵ a_{u w} - \frac{a _{uv} a _{v w}}{a _{vv}} .

(3)

Only 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

a d, a e, b e

. 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

ω (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]

Simplicial vertex (graph theory)

A simplicial vertex is a graph vertex whose graph neighbourhood is a clique. Every isolated vertex and every leaf of a graph qualifies. In the three-triangle chordal graph, initially

a, e

qualify, but

b

only becomes a simplicial vertex after deleting

a

. This is a property of adjacency in a graph; a vertex of a simplicial complex is an element of a different kind of structure.

Maximum cardinality search

Maximum cardinality search is a graph search in which an unselected vertex's score counts its already selected graph neighbours. Repeatedly select a vertex of maximum score, breaking ties arbitrarily, and update its unselected graph neighbours. On a chordal graph, the reverse selection order is a perfect elimination ordering. On

C_{4}

, selecting

(a, b, c, d)

instead yields candidate deletion order

(d, c, b, a)

;

d

's later graph neighbours

a, c

are not adjacent, so the clique check fails.^[ref]

Johnson graph ( $J (n, k)$ )

The Johnson graph has the

k

-element subsets of an

n

-element set as vertices, with two vertices adjacent exactly when their intersection has

k - 1

elements. Relabelling the ground set gives graph automorphisms. The maximal cliques of a Johnson graph allow reconstruction of those ground-set labels when the two clique sizes are different.

Distance in a Johnson graph ( $d (A, B) = k - ∣ A \cap B ∣$ )

One edge of a Johnson graph replaces one element of a

k

-subset, so it can increase intersection with a fixed target by at most one. Replacing each element outside the target by one missing target element gives a path reaching this lower bound. Equal-distance ordered pairs have equal sizes of intersection, the two differences and the remaining ground set; a permutation matching these four regions proves distance transitivity.

Maximal cliques of a Johnson graph ( $n - k + 1 and k + 1$ )

For

1 < k < n - 1

, the maximal cliques of

J (n, k)

are the families containing a fixed

(k - 1)

-subset, of size

n - k + 1

, and the families contained in a fixed

(k + 1)

-subset, of size

k + 1

. To see why these exhaust the possibilities, write two adjacent vertices as

D \cup {a}

and

D \cup {b}

. A common adjacent vertex either contains

D

or lies in

D \cup {a, b}

. A vertex of the first kind outside that union is not adjacent to a vertex of the second kind omitting an element of

D

, so a clique cannot mix these alternatives. For

J (n, 3)

and

n \geq 5

n \neq = 6

, the clique sizes

n - 2

and four distinguish the families containing pairs. Their incidence recovers

J (n, 2)

, whose stars of size

n - 1

distinguish the individual ground-set points from its triangular cliques.

Maximum degree ( $Δ (G)$ )

The maximum degree of a finite graph is the largest number of edges incident to one vertex. A bound

d

on degree bounds the number of vertices within distance

k

of a fixed vertex by

1 + d + \dots + d^{k}

. Such counting bounds turn a large vertex count into a lower bound on diameter.

Four-cycle counting by common neighbours ( $C_{4} (G) = \frac{1}{2} \sum_{i < j} (2 r _{ij})$ )

For a simple graph, let

r_{ij}

count the common neighbours of vertices

i, j

. Choosing two such neighbours makes a four-cycle, and each cycle is counted twice through its opposite pairs. The displayed identity follows even when extra edges are present, since cycles are counted as subgraphs rather than induced subgraphs. Also

\sum_{i < j} r_{ij} = \sum_{v} (2 d ( v ))

. Applying Cauchy-Schwarz inequality to degrees and Jensen inequality to common-neighbour counts gives extremal edge and cycle bounds.

Shortest path problem ( $min_{p : s ⇝ t} \sum_{e \in p} w_{e}$ )

The shortest path problem asks for a graph path from a source vertex

s

to a destination vertex

t

minimizing its total edge weight. Here

w_{e}

is the cost of traversing edge

e

, and costs add along the graph path. If no route exists, its shortest-path distance is

\infty

. With nonnegative edge weights, deleting cycles in a graph from a walk never increases its cost, so repetitions cannot improve the optimum.

Consider the undirected graph with vertex set

V = {A, B, C, D}

and the six edge weights

w_{A B} = 4, w_{A C} = 1, w_{CB} = 2, w_{B D} = 1, w_{C D} = 5, w_{A D} = 10.

Each edge can be traversed in either direction at the same cost. The direct graph path

A, D

costs

10

;

A, B, D

costs

4 + 1 = 5

;

A, C, D

costs

1 + 5 = 6

. The cheapest graph path is

A, C, B, D

, costing

1 + 2 + 1 = 4

. The remaining graph path

A, B, C, D

costs

11

, exhausting the possibilities without repeated vertices.

Figure 1.
The shortest path problem: three highlighted edges cost less than the direct connection
. **Details**.

Thus fewest edges and least total cost are different objectives. Breadth-first search minimizes the number of edges, which suffices when every edge has the same positive cost. Unequal nonnegative costs call for the Dijkstra algorithm. On a map, weights might be minutes rather than kilometres: a longer-looking route can arrive sooner. This is why a weighted graph separates the network's connections from what a particular journey costs.

Floyd-Warshall algorithm ( $d_{ij} \leftarrow min (d_{ij}, d_{ik} + d_{kj})$ )

The Floyd-Warshall algorithm computes all-pairs shortest graph path lengths in a finite weighted directed graph with no negative-length cycles in a graph. Initialize

d_{ii} = 0

, use the arc cost for each existing directed edge, and use

+ \infty

when no arc exists. For

k = 1, \dots, n

, update every ordered pair

(i, j)

by the displayed rule. The storage is

n^{2}

lengths and the running time is

O (n^{3})

For correctness, let

d_{ij}^{(k)}

be the shortest simple graph path length whose intermediate vertices lie among the first

k

. A shortest allowed graph path either avoids

k

or splits at its unique occurrence of

k

, giving the recurrence. Conversely, concatenate shortest paths through

k

and remove any repeated-vertex sections; each such closed walk has nonnegative length, so removal cannot increase the length. This proves equality. The update can be performed in place because

d_{kk} = 0

and the

k

th row and column remain unchanged during stage

k

If negative-length cycles in a graph are present, a shortest walk may not exist and the recurrence need not compute shortest simple graph paths. Two optimal subpaths can concatenate into a repeated-vertex walk with a negative cycle; deleting that cycle increases its length. A negative diagonal entry in the algorithm's final array detects this obstruction to finite shortest-walk distances.

Failure of uniform edge shifts to preserve shortest paths ( $w^{'} (P) = w (P) + C ∣ P ∣$ )

Adding the same constant

C

to every edge weight adds

C

times the number of edges to each path's cost. Routes with different edge counts need not retain their order. For example, edges

s \to t

s \to u

u \to t

of weights

1, - 2, 2

make the two-edge path optimal with cost zero. Adding three changes the direct cost to four and the two-edge cost to six. The graph is a Directed acyclic graph and all shifted weights are positive, yet the minimizing path changes.

Single-source shortest-path problem ( $d_{s} (v) = d (s, v)$ )

Compute shortest-path distances from one fixed source to every vertex, together with predecessor information when shortest paths exist. Dijkstra's algorithm handles nonnegative weights; the Bellman-Ford algorithm admits negative weights and detects reachable negative cycles. A Directed acyclic graph instead permits one pass in topological order.

DAG shortest-path algorithm

Initialize source distance to zero and other distances to infinity, then process vertices in topological order, relaxing their outgoing edges once. Every predecessor on a path to a vertex appears earlier, so induction through that ordering proves that its distance is final when processed. Negative weights are allowed because there are no directed cycles. With adjacency lists, topological sorting and all edge relaxations take

O (∣ V ∣ + ∣ E ∣)

time; predecessor pointers reconstruct paths.

Shortest-path distance ( $d (s, t) = in f_{P : s ⇝ t} \sum_{e \in P} w (e)$ )

The infimum of total edge weights over allowed walks from a source to a target. The value is

+ \infty

when no route exists. A negative cycle reachable from the source and able to reach the target makes it

- \infty

. In a finite graph without such a cycle, a finite distance is attained by a graph path, after removing non-improving repetitions.

Cycle erasure in minimum-weight walks

If every nontrivial closed subwalk has strictly positive weight, removing any repeated-vertex segment strictly decreases a walk's weight. Hence a minimum-weight walk must be a graph path, and it is a shortest path. Strictly positive edge weights are sufficient in an undirected graph. For a trail, positivity of every simple cycle is already sufficient: its first repeated-vertex segment is a cycle because no edge is repeated.

Under the usual unrestricted walk convention, positivity of simple cycles alone is insufficient. A graph consisting of one zero-weight edge

x y

has no cycles, but the walk

x, y, x, y

is a minimum-weight walk and is not a path. A zero-weight backtrack cannot be removed with a strict improvement. For nonnegative edge weights, one may erase such backtracks without increasing weight and obtain a shortest path, but cannot conclude that every minimum walk was already a path.

Shortest cycle by repeated shortest-path trees

In a positive-weight directed graph, run the Dijkstra algorithm from each source

s

and minimize

d_{s} (u) + w (u, s)

over closing edges. In an undirected graph, minimize

d_{s} (u) + w (u, v) + d_{s} (v)

only over edges absent from the current shortest-path tree. A tree edge would otherwise give a spurious traversal out and back. A non-tree candidate contains a genuine cycle no longer than its score, even when the two tree routes share a prefix.

For the undirected optimum, choose a shortest cycle and a source on it. If an incident cycle edge is absent from the tree, its candidate is bounded by the cycle length. Otherwise its two neighbours lie in distinct tree branches, and some edge on the remaining cycle segment crosses branches. That edge is non-tree; shortest distances to its endpoints are bounded by the two complementary cycle segments, again giving a candidate no greater than the optimum. Thus the minimum candidate equals the shortest-cycle length. Repeated Dijkstra algorithm runs take

O ((∣ V ∣^{2} + ∣ V ∣∣ E ∣) lo g (∣ V ∣ + 1))

running time with a binary heap.

Hop-bounded shortest-route recurrence ( $D_{r} (v) = min {D_{r - 1} (v), min_{(u, v) \in E} (D_{r - 1} (u) + w (u, v))}$ )

Let

D_{r} (v)

be the minimum weight of a route from a fixed source to

v

using at most

r

edges; repeated vertices are permitted. Initialise

D_{0}

to zero at the source and infinity elsewhere. Every feasible route either already uses at most

r - 1

edges or appends one edge to such a route, proving the displayed dynamic programming recurrence. Reading exclusively from the previous row enforces the edge budget. Negative cycles cause no unbounded objective because the budget is finite. Each round scans all edges, costing

O (m)

when only edge-incident vertices and the specified endpoints are processed. With nonnegative weights, cycle removal gives an equally good or better simple path within the budget.

Integer-weight shortest-path tie-breaking lemma ( $w^{'} (e) = ∣ V ∣ w (e) + 1$ )

In a finite graph with positive integral edge weights, replacing

w (e)

∣ V ∣ w (e) + 1

makes every transformed shortest path minimise original weight first and edge count second. Positive weights imply that an optimal route is simple, with at most

∣ V ∣ - 1

edges. Original integral path weights that differ have a gap of at least one; multiplication by

∣ V ∣

outweighs every possible difference in simple-path edge counts. Among equal-weight paths, only the added edge count differs. Thus a single ordinary shortest path computation solves lexicographic weight-and-hop minimisation.

Minimum-hop dominance for nearly unit weights

For a graph on

n

vertices with all edge weights in

[1, 1 + 1/ n]

, every minimum-weight shortest path has the smallest possible number of edges. Indeed, positivity permits a simple optimum, and a simple

r

-edge path weighs at most

r + r / n < r + 1

for

r \leq n - 1

, while any path with more edges weighs at least

r + 1

. A breadth-first search followed by weighted dynamic programming along increasing-hop edges therefore solves the single-source problem in

O (∣ V ∣ + ∣ E ∣)

time. Choosing an arbitrary breadth-first tree alone is insufficient: equal-hop routes may still have different weights.

Shortest-path pursuit distance bound ( $d_{t + 1} \leq d_{t} - a + b$ )

Suppose two pieces occupy a common connected component of a graph in an unweighted undirected graph. For integers

a > b \geq 0

, in each round an evader moves at most

b

edges, then a pursuer moves up to

a

edges along a shortest path to the new evader position, stopping upon capture. Let

d_{t}

be their finite graph distance at a surviving round boundary.

The triangle inequality bounds the separation after the evader moves by

d_{t} + b

. If that separation is at most

a

, the pursuer captures it. Otherwise the pursuer reduces it by exactly

a

, giving

1 \leq d_{t + 1} \leq d_{t} - (a - b) .

Hence every surviving history has at most

⌊(d_{0} - 1) / (a - b)⌋

rounds. With a finite branching factor, the surviving search tree is finite and depth-first tree search becomes a complete search algorithm. This does not make its first goal optimal for arbitrary rewards. Initial reachability is essential: an infinite graph distance supplies no decreasing finite bound.

Bottleneck shortest path problem ( $min_{P : x ⇝ y} max_{e \in E (P)} ℓ (e)$ )

Unlike the sum in the usual shortest path problem, the bottleneck cost of a nonempty graph path is its largest edge weight. The optimum is the smallest threshold at which the endpoints become connected by edges of weight at most that threshold. Sorting edges and increasing the threshold, with a disjoint-set data structure maintaining components, finds this value. The minimax path property of a minimum spanning tree provides a single tree representing such optimal routes for every pair of vertices.

Shortest-path tree

A shortest-path tree rooted at a source vertex is a spanning tree whose unique tree route from the source to every vertex solves the shortest path problem in the original weighted graph. Dijkstra's algorithm constructs one for a finite connected graph with nonnegative edge lengths, recording a predecessor whenever a distance improves. It need not be a minimum spanning tree: one minimizes each source-route length, the other the total weight of the tree's edges.

Figure 1.
Signed shortest paths can conflict; positive predecessor choices form a tree
. Original diagrams and generic model calculations generated by the adjacent Python script. **Details**.

Positive-weight shortest-path predecessors form a tree ( $d (u) = d (p (u)) + w (p (u) u) > d (p (u))$ )

In a finite connected graph with strictly positive edge weights, choose any shortest path from a root

v

to every other vertex

u

, and let

p (u)

be its penultimate vertex. Every prefix is shortest: a better prefix followed by the final edge would give a cheaper walk, whose positive-weight cycles can be erased to give a cheaper path. Thus the displayed distance identity holds.

Following predecessors strictly decreases the shortest-path distance, so no predecessor cycle is possible. Since every nonroot vertex has a predecessor, every chain reaches the root. Opposite predecessor choices cannot select the same undirected edge, again by strict distance decrease. The selected graph is connected and has exactly one edge per nonroot vertex, so is a spanning tree. Along its root paths the distance differences telescope, proving that it is a shortest-path tree even if the original shortest paths were chosen independently.

Signed edge weights can prevent a shortest-path tree

In a triangle with root

v

, assign

w (v a) = w (v b) = 2

and

w (ab) = - 1

. Among graph paths, the unique shortest path from

v

a

v, b, a

, and that from

v

b

v, a, b

, both of weight one. A shortest-path tree would have to contain all three edges, impossible for a tree. The example uses shortest simple paths; arbitrary walks can have unboundedly negative weight by repeatedly traversing the negative edge.

Shortest path

A graph path of minimum total edge weight between its endpoints, among the permitted paths. In an unweighted graph, its weight is the number of edges. A shortest path need not be unique.

Label-setting shortest-path algorithm

An algorithm that makes each vertex's distance permanent once it is selected. With nonnegative directed edge lengths, the Dijkstra algorithm selects the unfinalized vertex with least tentative distance; a shorter route through another unfinalized vertex is impossible because its remaining route has at least that next tentative distance. For an all-to-one problem, incoming directed edges to the selected vertex are relaxed. Negative lengths can invalidate this finalization argument.

Bellman inequalities ( $d_{i} \leq c_{ij} + d_{j}$ )

The Bellman inequalities turn local directed edge checks into a global certificate for the shortest path problem. Here the convention is all-to-one: every journey ends at a fixed vertex

r

, and

c_{ij}

is the cost of the original directed edge

i \to j

. Work in a finite directed graph with finite real costs. Write

L_{i}

for candidate labels, normalized by

L_{r} = 0

, on the vertices that can reach

r

. A feasible potential means precisely that these finite labels satisfy

L_{i} \leq c_{ij} + L_{j}

for every directed edge within that set. These labels give lower bounds on costs to

r

. A discovered directed path of cost

U_{i}

instead gives an upper bound. The following constructed graph shows both bounds and the exact distances between them; its weights are illustrative costs, not measured travel data.

Figure 1.
Bellman inequalities and explicit directed paths certify distances to $r$ from opposite sides
. **Details**.

The arrows in the picture point toward the destination, whereas edge relaxation propagates an improved label in the opposite direction: an improved

d_{j}

can lower

d_{i}

. In the pictured graph, the directed paths from

a

r

cost

7

2 + 3 = 5

, and

2 - 2 + 4 = 4

. Thus

δ (a, r) = 4

. The candidate

L = (3, 1, 3, 0)

in vertex order

(a, b, c, r)

is feasible, but underestimates the exact distances

(4, 2, 4, 0)

. Merely satisfying the Bellman inequalities does not make a candidate exact.

Why do they give lower bounds? Along any directed path

i = v_{0} \to v_{1} \to \dots \to v_{k} = r

, successive substitution gives

L_{i} \leq \sum_{ℓ = 0}^{k - 1} c_{v_{ℓ} v_{ℓ + 1}} + L_{r} = \sum_{ℓ = 0}^{k - 1} c_{v_{ℓ} v_{ℓ + 1}} .

The same calculation works for a directed walk, with repeated vertices allowed. Taking the infimum of route costs gives

L_{i} \leq δ (i, r)

. A discovered route gives

δ (i, r) \leq U_{i}

. If the bounds meet,

L_{i} = U_{i}

, they certify an optimum without enumerating routes. Equivalently, check the Bellman inequalities for the proposed distances and exhibit directed paths realizing them. The authored Bellman-Ford algorithm implementation checks the corresponding single-source inequalities and equality on recorded route edges; reversing every directed edge gives this all-to-one convention.^[ref]

For the exact labels in the picture, the slack

c_{ij} + d_{j} - d_{i}

is respectively

0, 3, 1, 0, 0

a \to b

a \to r

b \to r

b \to c

c \to r

. Zero slack means equality; the zero-slack directed path

a \to b \to c \to r

realizes the cost

4

. This is the useful beauty of the certificate: a few local inequalities rule out every cheaper journey, while one explicit journey attains the bound.

Keep unreachable vertices separate:

δ (i, r) = \infty

when no directed path to

r

exists, and a finite lower bound alone cannot certify that fact. Extended labels can use

\infty + c = \infty

for finite

c

, but never compute a slack as

\infty - \infty

. If

i

can reach a negative-cost directed cycle and then reach

r

, repeatedly traversing the directed cycle makes route costs unbounded below: their infimum is

- \infty

, with no finite shortest directed walk. A finite feasible potential on such a directed cycle is impossible, since summing its Bellman inequalities would give

0 \leq \sum c_{ij} < 0

. A negative-cost directed cycle that cannot reach

r

does not affect distances to

r

. These are statements about unrestricted directed walks; requiring a directed path with no repeated vertices is a different optimization problem when negative-cost directed cycles exist.^[ref]

For the single-source convention, the same original directed edge

u \to v

instead gives

L (v) \leq L (u) + w_{uv}

with

L (s) = 0

, a lower bound on distance from

s

. The endpoint carrying the label on the left therefore changes with the direction of the problem.

Label-correcting shortest-path algorithm

An algorithm whose tentative distance labels may be revised repeatedly until all relevant Bellman inequalities hold. Bellman-Ford algorithm uses this approach: a label is an upper bound supplied by a discovered directed path, and relaxing an directed edge can replace it with a shorter discovered directed path. A finite label is not declared permanent merely because it has been processed.

Bellman-Ford algorithm ( $δ (s, v)$ )

The Bellman-Ford algorithm solves the single-source shortest path problem in a finite directed graph with finite real edge weights, allowing negative weights. It repeatedly applies edge relaxation, so an improved tentative distance can improve its neighbours on a later visit. This makes it a label-correcting shortest-path algorithm.^[ref] If no negative-cost directed cycle is reachable from the source, at most

∣ V ∣ - 1

complete passes suffice for all distances; a further check detects a reachable negative-cost directed cycle.^[ref]

There are two orientations to keep distinct. The usual single-source problem asks for distances from

s

, extending routes along outgoing directed edges. The Bellman inequalities above instead concern distances to a sink

r

, prepending incoming directed edges to known routes. The All-to-one Bellman-Ford recurrence below preserves that convention. Reversing every directed edge, with its weight unchanged, converts one problem into the other.

Here is an original single-source example with source

S

, vertex set

V = {S, A, B, C, T}

, and precisely these directed edges:

w_{S A} = 4, w_{SB} = 5, w_{A B} = - 2, w_{BC} = 3, w_{CT} = 2, w_{A T} = 8.

The negative edge

A \to B

is harmless: this directed graph has no directed cycle. Its best route to

T

S \to A \to B \to C \to T

, of cost

4 - 2 + 3 + 2 = 7

. The other routes to

T

cost

12

through

S, A, T

and

10

through

S, B, C, T

Figure 1.
Four in-place Bellman-Ford algorithm passes propagate an improvement across a negative-weight edge
. **Details**.

Initialize

d (S) = 0

and the other tentative distances to

\infty

. In each pass apply single-source edge relaxation,

d (v) \leftarrow min {d (v), d (u) + w_{uv}}

, scanning in the order

A \to T

C \to T

B \to C

A \to B

S \to B

S \to A

. Skip a candidate with

d (u) = \infty

. The figure records labels after each complete pass and uses current labels immediately: it is an in-place trace. In pass 2,

B \to C

still uses

d (B) = 5

, giving

8

; only later does

A \to B

lower

B

2

. Pass 3 carries that improvement to

C

, and pass 4 carries it to

T

. The final labels in order

(S, A, B, C, T)

are

(0, 4, 2, 5, 7)

; the final shortest-path predecessors are

S, A, B, C

for

A, B, C, T

respectively.

The scan order explains the delay. Scanning instead as

S \to A

S \to B

A \to B

B \to C

C \to T

A \to T

gives those same final labels in just one in-place pass. The Synchronous Bellman-Ford recurrence has a precise bound on the number of edges used by a recorded route; an in-place pass can propagate along several edges and need not have that interpretation. Both implementations have the

∣ V ∣ - 1

pass guarantee under the stated no-reachable-negative-cycle hypothesis.

With a stored list of edges, complete-pass Bellman-Ford algorithm has time complexity

O (∣ V ∣∣ E ∣ + ∣ V ∣)

and uses

O (∣ V ∣)

extra space for labels and shortest-path predecessors, using Big O notation and constant-cost arithmetic. The extra

∣ V ∣

accounts for initialization even when

E

is empty. A pass with no strict decrease permits early termination. A queue variant instead revisits outgoing edges of vertices whose labels improved; the authored implementation provides this alternative and has

O (∣ V ∣∣ E ∣)

worst-case running time on its usual nontrivial instances.^[ref] For nonnegative weights, the Dijkstra algorithm and its existing distance-frontier figure explain how permanent labels can avoid these repeated passes; the existing edge relaxation figure illustrates one update at a time.

Synchronous Bellman-Ford recurrence ( $D_{k} (v) = min {D_{k - 1} (v), min_{(u, v) \in E} (D_{k - 1} (u) + w_{uv})}$ )

For the single-source problem, let

D_{k} (v)

be the minimum cost of a directed walk from

s

v

using at most

k

edges. Set

D_{0} (s) = 0

and

D_{0} (v) = \infty

for

v \neq = s

, use

\infty + c = \infty

for finite

c

, and let a minimum over an empty set be

\infty

. Then

D_{k} (v) = min {D_{k - 1} (v), min_{(u, v) \in E} (D_{k - 1} (u) + w_{uv})} .

Every entry on the right comes from the previous round, requiring separate old and new arrays. The proof is the last-edge decomposition: a permitted directed walk either already uses at most

k - 1

edges, or ends with some

u \to v

after a prefix using at most

k - 1

. Conversely, each candidate describes a permitted directed walk. This dynamic programming viewpoint gives an exact meaning to every intermediate label, even when negative-cost directed cycles exist. Apply the formula to the source too: its initial zero is not a permanent constraint.

If no negative-cost directed cycle is reachable from

s

, removing repeated-vertex portions of a directed walk cannot increase its cost. Whenever a destination is reachable, some shortest directed path therefore uses at most

∣ V ∣ - 1

edges, and

D_{∣ V ∣ - 1} (v) = δ (s, v)

. Unreachable vertices keep distance

\infty

. For in-place passes, every finite label still comes from a discovered directed walk; moreover, pass

k

has offered every prefix of length

k

of a shortest directed path, regardless of scan order. Its labels can improve faster than the synchronous labels, while the same

∣ V ∣ - 1

upper bound on passes remains valid. This is why repeated local corrections eventually settle a global shortest path problem.

Bellman-Ford negative-cycle detection

A negative-cost directed cycle matters to a particular destination

v

precisely when it is reachable from

s

and can itself reach

v

.^[ref] Repeating it

m

times adds

m

times its negative total cost to a route. Thus the infimum of directed walk costs is

- \infty

, rather than the cost of a finite shortest directed walk. The distinction is about reachability, not simply the presence of a negative edge or a negative-cost directed cycle anywhere in the graph.

Add

C \to A

of weight

- 4

to the worked example. Now

A \to B \to C \to A

has total weight

- 2 + 3 - 4 = - 3

. Add also an isolated vertex

U

with a self-loop of weight

- 1

. From

S

, the distances of

A, B, C, T

are

- \infty

, because all four are reachable from the first negative-cost directed cycle. The source retains distance

0

: no directed edge leads back to

S

. The unreachable

U

retains distance

\infty

, despite its negative-cost self-loop.

Figure 1.
Relevant negative-cost directed cycles: descendants from a source become ancestors when every directed edge is reversed
. **Details**.

For example,

m

extra laps before proceeding to

T

give costs

7 - 3 m

. This construction also shows why requiring a directed path with no repeated vertices would change the problem: only directed walks permit arbitrarily many laps. Merely finding one reachable negative-cost directed cycle does not justify setting every reachable label to

- \infty

;

S

in the figure is a counterexample.

To detect and classify, perform

∣ V ∣ - 1

full passes without clamping any label, then test all directed edges against a fixed copy of the resulting labels. Collect heads

v

of edges

u \to v

satisfying

d (u) < \infty

and

d (u) + w_{uv} < d (v)

. An empty collection certifies that no negative-cost directed cycle is reachable from

s

. Otherwise run graph search forwards from all collected vertices: precisely the reached vertices have distance

- \infty

. A vertex unreachable from

s

still has distance

\infty

; each remaining vertex has its finite shortest distance.

Why is this classification exact? Every unaffected reachable vertex already has its shortest distance after

∣ V ∣ - 1

passes, since any route ending there avoids reachable negative-cost directed cycles. Thus it cannot be the head of a strict improvement, or be reached from such a head. Conversely, all vertices on a reachable negative-cost directed cycle have finite labels by that time. If none of its edges could improve a label, summing

d (v) \leq d (u) + w_{uv}

around it would imply

0 \leq \sum w_{uv} < 0

. At least one of its heads is therefore collected, and the forward graph search reaches the entire directed cycle and every affected descendant. Detecting a directed cycle alone and marking its descendants are separate tasks; finite intermediate labels in the affected region are not answers.

All-to-one Bellman-Ford recurrence ( $d_{i}^{(k)} = min {d_{i}^{(k - 1)}, min_{(i, j) \in E} (c_{ij} + d_{j}^{(k - 1)})}$ )

Keep the original all-to-one orientation of the Bellman inequalities:

d_{i}^{(k)}

concerns routes from

i

to a fixed sink

r

, and

c_{ij}

belongs to the original directed edge

i \to j

. Initialize

d_{r}^{(0)} = 0

and

d_{i}^{(0)} = \infty

for

i \neq = r

. The synchronous dynamic programming recurrence is

d_{i}^{(k)} = min {d_{i}^{(k - 1)}, min_{(i, j) \in E} (c_{ij} + d_{j}^{(k - 1)})} .

It prepends the first edge of a route instead of appending the last:

d_{i}^{(k)}

is the minimum cost of a directed walk from

i

r

using at most

k

edges. In particular, improving

d_{j}

can improve labels on incoming directed edges

i \to j

. The same original directed edge therefore updates its tail in this convention, whereas single-source edge relaxation updates its head.

If no negative-cost directed cycle can reach

r

∣ V ∣ - 1

rounds suffice for every distance to

r

, and

d_{r}^{(k)} = 0

automatically. This hypothesis concerns directed paths from the cycle to the sink, not paths from the sink to the cycle. In the base example with its original arrows and sink

T

, the distances in order

(S, A, B, C, T)

are

(7, 3, 5, 2, 0)

. Once

C \to A

of weight

- 4

is added,

S, A, B, C

instead have distance

- \infty

T

, while

T

keeps distance

0

and

U

keeps

\infty

More generally,

δ (i, r) = - \infty

precisely when

i

can reach a negative-cost directed cycle that can reach

r

. Thus the affected vertices are the ancestors of such a directed cycle. A negative-cost directed cycle unable to reach

r

is irrelevant. Reversing all arrows makes

r

a single source, turns these ancestors into descendants, and makes the detection and forward graph search above directly applicable. The right panel of the figure uses that reversal with sink

S

; its distances to

S

equal the left panel's distances from

S

Do not force the root to remain zero outside the hypothesis. Consider the two directed edges

r \to a

of cost

0

and

a \to r

of cost

- 1

, with sink

r

. The recurrence gives

d_{a}^{(1)} = - 1

and

d_{r}^{(2)} = - 1

: the latter records one lap of a negative-cost directed cycle through

r

. Repetition makes both unrestricted distances

- \infty

. Clamping

d_{r}

at zero and omitting its update would instead leave the stationary labels

(d_{r}, d_{a}) = (0, - 1)

, concealing that behaviour. Initialization specifies the cost of the empty directed walk; it does not forbid cheaper nonempty returns to the root. Cycle detection must test every relevant directed edge, including those whose relaxation updates the root.

Dijkstra algorithm ( $d (v) = dist (s, v)$ )

The Dijkstra algorithm solves the single-source shortest path problem in a finite graph with nonnegative edge weights, finding distances to all reachable vertices. Start with tentative distance

d (A) = 0

and

d (v) = \infty

elsewhere. Repeatedly choose the unfinalized vertex with least tentative distance, declare that label permanent, and perform edge relaxation on its outgoing edges. For an undirected graph, inspect both directions. A finite tentative distance always records the cost of a discovered graph path, but can improve before finalization.

In our example, finalizing

A

discovers

C

1

B

4

, and

D

10

. Choose

C

next: edge relaxation through

C

lowers

B

1 + 2 = 3

and

D

1 + 5 = 6

. Choose

B

: edge relaxation through

B

lowers

D

3 + 1 = 4

. Finally choose

D

. The permanent distances are therefore

A : 0

C : 1

B : 3

D : 4

; the evolving tentative distances were

B : 4 \to 3

and

D : 10 \to 6 \to 4

Figure 1.
Tentative distances fall until the Dijkstra algorithm makes each label permanent
. **Details**.

Store a shortest-path predecessor whenever edge relaxation improves a label. The final table contains enough information to reconstruct routes, rather than merely their costs:

Vertex	Distance from $A$	Shortest-path predecessor	Finalization order
$A$	$0$	None: source	$1$
$C$	$1$	$A$	$2$
$B$	$3$	$C$	$3$
$D$	$4$	$B$	$4$

Following shortest-path predecessors backwards gives

D, B, C, A

; reversing the order gives

A, C, B, D

. If only this destination matters, stop when

D

is finalized. Stopping when

D

is first discovered would incorrectly return

10

. If the smallest remaining tentative distance is

\infty

, all remaining vertices are unreachable.

Why is the permanent choice safe? Suppose the selected vertex

u

had a cheaper graph path. Let

y

be the first unfinalized vertex on that graph path. Its preceding vertex was finalized, so edge relaxation has already offered

y

a label no larger than that prefix's cost. Nonnegative remaining edge weights make the whole cost at least this prefix's cost; selection gives

d (u) \leq d (y)

. A cheaper graph path would contradict these comparisons. Zero weights are allowed; ties can be resolved arbitrarily. This is the reason the label-setting shortest-path algorithm works, rather than a lucky feature of the drawing.

Negative weights break that reasoning. In a directed graph with

s \to u

costing

2

s \to v

costing

5

, and

v \to u

costing

- 4

, the Dijkstra algorithm would finalize

u

2

before discovering the cheaper cost

1

. The Bellman-Ford algorithm handles negative edge weights when no relevant negative directed cycle exists.

With an adjacency list and an indexed binary heap implementing a priority queue, the time complexity is

O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)

for

∣ V ∣ \geq 2

, using Big O notation. Each vertex is extracted at most once, each edge is inspected once per direction, and each successful edge relaxation decreases a heap key in

O (lo g ∣ V ∣)

time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses

O (∣ V ∣)

space beyond the graph. Simply scanning all remaining vertices gives

O (∣ V ∣^{2} + ∣ E ∣)

instead.^[ref]^[ref]

The 1959 paper presents the shortest path problem as its second problem, after the minimum spanning tree problem, and grows known shortest routes in increasing distance order.^[ref] In his later recollection, Dijkstra dated the shortest-route discovery to 1956: a demonstration for the ARMAC computer used a simplified Dutch railway map and printed the route between towns. A practical request became an enduring algorithm because the same distance rule applies to any suitable graph.^[ref]

Minimum-hop shortest paths ( $min_{lex} (weight, edge count)$ )

Among paths of minimum total weight, choose the fewest edges. Store a lexicographic order pair

(d, h)

and extend it across weight

w

(d + w, h + 1)

. For positive edge weights, every extension strictly increases its first component, so Dijkstra's algorithm settles these pairs correctly when its priority queue and relaxation both compare the full pair. Equal total weight then selects the smaller hop count; arbitrary vertex-name tie-breaking does not express this objective.

Tentative distance ( $d (v)$ )

A tentative distance

d (v)

is the cheapest cost so far recorded by a shortest path problem algorithm. For the single-source convention, initialize

d (s) = 0

and

d (v) = \infty

elsewhere. Every finite label is the cost of a discovered route from

s

v

, so

δ (s, v) \leq d (v) .

It is an upper bound supplied by an actual route, not a guess that might be too low. The loop invariant follows directly from edge relaxation: extending a discovered route to

u

u \to v

supplies another discovered route. The usual label initialization and this safety property are stated and proved in the authored MIT notes.^[ref]

In the trace under edge relaxation,

d (t) = 10

first records the direct directed path

s \to t

. Later

d (t) = 8

records

s \to a \to t

, and finally

d (t) = 3

records

s \to b \to a \to t

. Each label is a usable route cost, but the first two are not shortest. An infinite tentative distance means no route has yet been discovered; only a completed search establishes unreachability. The isolated vertex

z

in that example remains at

\infty

In a directed graph, the discovered route is formally a directed walk, which may repeat vertices; in the pictured acyclic graph it is always a directed path. Negative-cost directed cycles can keep supplying cheaper directed walks without a finite optimum. In the all-to-one convention, the same meaning applies to discovered routes from

i

r

. Do not confuse either version with the lower bounds supplied by feasible potentials in the Bellman inequalities: one records something achievable, the other rules out anything cheaper.

Edge relaxation ( $d (v) \leftarrow min {d (v), d (u) + w_{uv}}$ )

Edge relaxation tests whether extending a recorded route by one directed edge improves a tentative distance. For a single source

s

and an original directed edge

u \to v

of weight

w_{uv}

, form the candidate

q = d (u) + w_{uv}

. If

d (u)

is finite and

q < d (v)

, replace

d (v)

q

and record the shortest-path predecessor

π (v) = u

. Otherwise leave both unchanged. The minimum formula in the header gives the resulting label in either case. The authored implementation uses this strict comparison and records the incoming directed edge.^[ref]

Figure 1.
Edge relaxation lowers discovered-route costs, including across a negative-weight directed edge
. **Details**.

The table lists labels after each specified operation, keeping

d (s) = 0

throughout this constructed acyclic graph. Relaxing

a \to t

first offers

6 + 2 = 8

. Relaxing

b \to a

then offers

2 - 1 = 1

, lowering

a

from

6

1

; revisiting

a \to t

now offers

1 + 2 = 3

. Finally

b \to t

offers

2 + 7 = 9

, so the label

3

stays. Changing a label can make a previously checked outgoing directed edge worth checking again. This trace illustrates the operation itself, with a deliberately specified order, rather than a run of the Dijkstra algorithm.

A single edge relaxation does not require nonnegative weights: its candidate is the cost of a real extended directed walk, even when the last directed edge has negative weight. Nonnegative weights are needed by the Dijkstra algorithm to make its selected minimum tentative distance permanent. The Bellman-Ford algorithm permits negative weights and revisits labels; its authored implementation also checks for reachable negative-cost directed cycles.^[ref]^[ref]

For the all-to-one convention of the Bellman inequalities, relax the same original directed edge

i \to j

d_{i} \leftarrow min {d_{i}, c_{ij} + d_{j}}

. This prepends

i \to j

to a discovered route from

j

r

, and improves the tail label

d_{i}

, not the head label

d_{j}

. Skip the operation when

d_{j} = \infty

. In exact arithmetic, a full pass over all relevant directed edges with no improvement establishes all their Bellman inequalities; combined with the discovered-route upper bounds, this certifies finite distances. One unsuccessful operation establishes only that this particular candidate did not improve its label at that moment.

Shortest-path predecessor ( $π (v)$ )

A shortest-path predecessor

π (v)

records the previous vertex on a chosen route from source

s

v

. When edge relaxation strictly improves

d (v)

through

u \to v

, set

π (v) = u

. For a multigraph, store the actual directed edge, since two edges with the same endpoints can have different weights. Initialize all vertices, including the source, without a shortest-path predecessor. The authored implementation reconstructs a route by following these incoming edges backwards, then reversing their order.^[ref]

At the end of the edge relaxation trace,

π (t) = a

π (a) = b

, and

π (b) = s

. Following them gives

t, a, b, s

, so the forward directed path is

s \to b \to a \to t

, of cost

2 - 1 + 2 = 3

. This makes the distance useful: a number tells us the best cost, whereas the shortest-path predecessors tell us which connections to take. In the Dijkstra algorithm, reconstruct a destination's shortest route after its label becomes permanent. In a label-correcting shortest-path algorithm, wait for convergence and the appropriate negative-cost directed cycle check. During correction, a predecessor's label may have changed since its child's last update: immediately after

b \to a

in the trace, the current chain to

t

costs

3

although

d (t)

still records the earlier discovered route of cost

8

Strict improvement is a useful guard against directed cycles in the recorded pointers. Consider

s \to a

and

s \to b

of cost zero, followed by

a \to b

and

b \to a

, also of cost zero. After the first two edge relaxations, both labels are zero and both shortest-path predecessors are

s

. If equality also allows pointer replacement, the last two operations can set

π (b) = a

and

π (a) = b

: following pointers loops forever despite correct distance labels. Keeping the old pointer on ties prevents this example; choosing among equal-cost routes requires a separate rule that preserves a route to the source. Strict improvement alone does not protect against reachable negative-cost directed cycles, which can force endless decreases. Equality on recorded edges plus the Bellman inequalities certifies route costs only when the pointer chains actually terminate at the source.

For all-to-one distances to

r

, record a next vertex

j

whenever relaxing

i \to j

improves

d_{i}

. Follow these successors forward in the original directed graph to reach

r

. They are shortest-path predecessors when viewed in the reversed directed graph; keeping the direction convention explicit prevents returning a route whose arrows point the wrong way.

Graph property

A graph property is a class of finite graphs closed under isomorphism. Its labelled order-

n

slice consists of members on vertex set

[n]

. Closure under taking arbitrary subgraphs and closure under taking only induced subgraphs lead respectively to subgraph-closed graph properties and hereditary graph properties.

Common-center graph property ( $STAR_{n} (G)$ )

All edges of a simple undirected graph have at least one common endpoint. The empty graph is included when there is at least one vertex, and isolated vertices are permitted. This is the star predicate with isolated vertices allowed; a connected star graph is a special case. Its decision-tree depth is the full number

(2 n)

of edge bits for

n \geq 3

Certificates for the common-center graph property ( $C_{1} = (2 n - 1), C_{0} = 3$ )

For

n \geq 3

, a full star graph requires every nonincident edge to be certified absent, and fixing those bits suffices. Rejection is certified by at most three present edges with empty common intersection; a triangle needs all three. Hence query certificate complexity is

max {3, (2 n - 1)} = Θ (n^{2})

for this property.

Alternating count of common-center graphs ( $\sum_{G} (- 1)^{∣ E (G) ∣} STAR_{n} (G) = (n - 1) (n - 2) /2$ )

For

n \geq 3

, count the empty graph once, all one-edge graphs once, and each larger accepted graph under its unique center. The latter weighted contribution is

n (n - 2)

, giving

1 - (2 n) + n (n - 2)

. Its nonzero value proves evasiveness by the alternating-sum criterion for decision-tree evasiveness.

Speed of a graph property ( $∣ P_{n} ∣$ )

The speed counts the labelled graphs with a given property on vertex set

[n]

. For proper unbounded hereditary graph properties, its base-two logarithm has leading term

(1 - 1/ r) (2 n)

, where

r

is the property's colouring number.

Hereditary graph property

A hereditary graph property is closed under taking induced subgraphs. It can be described by forbidden induced graphs. Unlike subgraph closure, this condition allows edges to be essential to membership. Its colouring number of a hereditary graph property governs its quadratic enumeration rate.

Colouring number of a hereditary graph property ( $r (P) = max {a : C (a, b) \subseteq P for some b}$ )

This parameter measures the largest completely unrestricted clique-independent partition class contained in the property. It is zero for bounded-order hereditary classes and infinite for all graphs. For proper unbounded classes it is a positive integer; it differs from the degeneracy-based colouring number of an individual graph.

Hereditary graph enumeration theorem ( $∣ P_{n} ∣ = 2^{(1 - 1/ r (P) + o (1)) (2 n)}$ )

For a proper hereditary graph property with unbounded orders, the colouring number determines the leading labelled speed. The lower bound comes from one contained clique-independent partition class. For the upper bound, forbid one induced graph from each next-size partition type and use the induced regularity template lemma. Its intermediate-pair graph is clique-free, and sparse or almost-complete pairs have negligible entropy. Bounded-order properties have colouring number zero and are outside this formula.

Clique-independent partition class ( $C (a, b)$ )

Graphs in

C (a, b)

admit a partition into

a

total classes, of which

b

are designated cliques and

a - b

are designated independent sets. Cross edges are arbitrary and empty classes are allowed. Balanced cross-edge choices give quadratic labelled speed coefficient

1 - 1/ a

. Comparing this count with every

(a + 1)

-class type shows that the hereditary colouring number of this class is exactly

a

Subgraph-closed graph property