= Perfect elimination ordering
A <perfect elimination ordering> of a finite <simple graph> $G=(V,E)$ is a <permutation> $(v_1,\ldots,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 (graph theory)> in the remaining <induced subgraph> $G[\{v_i,\ldots,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 (graph theory)>, and every <induced subgraph> of a <chordal graph> is a <chordal graph>; repeatedly deleting such a <vertex> supplies the ordering.<An Introduction to Chordal Graphs and Clique Trees by Jean R. S. Blair and others>[§2.2; Theorem 2.2]{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>, using
$$
V=\{a,b,c,d,e\},\qquad E=\{ab,ac,bc,bd,cd,ce,de\}.
$$
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 $\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\}$.
\Image[/chordal-perfect-elimination-triangle-chain.png]
{title=A <perfect elimination ordering> removes three overlapping triangles without <fill-in>; choosing the central <vertex> first adds three <edges>}
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.<Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and others>[§4.1–4.2; Algorithm 4.2]{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_{uw}\longleftarrow a_{uw}-\frac{a_{uv}a_{vw}}{a_{vv}}.
$$
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.<Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and others>[§9.1; equation 9.2; Theorem 9.1]{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>.<Algorithmic Aspects of Vertex Elimination on Graphs by Donald J. Rose and others>[pp. 266–283; abstract]{ref}
Back to article page
