Simplicial Vertices and Elimination Orderings

Simplicial Vertices and Elimination Orderings

A chordal graph can contain many overlapping cliques, so a useful way to examine its structure is to remove vertices one at a time while keeping track of the graph that remains. The vertices suitable for removal have a precise local property: their neighbors already form a clique. Recording a sequence of such removals gives a perfect elimination ordering, or PEO.

All graphs in this tutorial are finite and simple. A set of vertices is a clique if every two distinct vertices in the set are adjacent; the empty set and every one-vertex set are cliques. For \(S\subseteq V(G)\), the induced subgraph \(G[S]\) has vertex set \(S\) and contains exactly those edges of \(G\) whose two endpoints lie in \(S\). A graph is chordal if it has no induced cycle of length at least \(4\). We use that definition here, without proving the characterization of chordal graphs by elimination orderings.

The condition concerns the neighbors that remain, not necessarily all the neighbors in the original graph. Deleting \(v_1,\ldots,v_{i-1}\) leaves precisely the induced subgraph on \(\{v_i,\ldots,v_n\}\). If \(v_i\) has no remaining neighbors, its neighborhood is empty and is a clique, so it is simplicial. The empty graph has the empty ordering, which is a PEO by the vacuous condition.

Deletion and the Ordering Condition

The definition can be used directly as a procedure. Start with a graph \(G\); if the current graph has a simplicial vertex, choose one, record it, and delete it. Deletion means taking the induced subgraph on the vertices left over: it does not add edges between former neighbors.

Proof. Suppose first that the sequence is produced by the deletion procedure. Immediately before \(v_i\) is removed, the current graph consists of \(v_i,\ldots,v_k\) together with the vertices \(R\) that are not in the sequence. The procedure permits the removal only when \(v_i\) is simplicial in that graph, giving the stated condition. Conversely, suppose the stated condition holds at each step. Before step \(i\), successive induced-subgraph deletions have left exactly \(G[\{v_i,\ldots,v_k\}\cup R]\): this is true initially, and deleting \(v_i\) leaves the induced subgraph on the remaining vertices. The condition therefore says that the next chosen vertex is simplicial in the current graph, so the procedure can perform every deletion in the sequence. When \(R\) is empty, the condition is exactly the definition of a PEO. \(\square\)

This is a correctness statement for the deletion method, not a guarantee that a choice will always be available. If the graph has a PEO, its first vertex is simplicial; if one is not available, the method cannot continue from that current graph. Whether chordality guarantees a PEO is the subject of the chordal-graph characterization, not an assumption needed for the examples below.

Proof. Let \(S\) be the vertex set of a nonempty induced subgraph \(G[S]\). Restrict the ordering \(v_1,\ldots,v_n\) to the vertices in \(S\), retaining their original relative order. Let \(v_j\) be the first vertex of this restricted ordering. Every neighbor of \(v_j\) in \(G[S]\) occurs later than \(v_j\) in the original ordering, because no vertex of \(S\) occurs earlier in the restricted ordering. The PEO condition says that all later neighbors of \(v_j\) in \(G\) form a clique. The neighbors in \(G[S]\) are a subset of those later neighbors, and any subset of a clique is a clique. Thus \(v_j\) is simplicial in \(G[S]\). Since \(S\) was arbitrary and nonempty, the proposition follows. \(\square\)

A useful consequence is that a PEO gives more than one good vertex in the original graph: after restricting the ordering, it gives a simplicial vertex in every nonempty induced subgraph. This is often a convenient way to check whether a proposed ordering could possibly work.

Constructing Orderings in Small Graphs

What the Ordering Does—and Does Not—Say

A PEO is a property of an ordered graph, not a claim that every ordering works. Even in a graph with a PEO, changing the order can make a vertex’s later neighbors fail to form a clique. Likewise, being simplicial at the start does not mean a vertex stays simplicial after arbitrary changes to the graph. The test is always local to the current induced subgraph.

Consider the following contrasting graph, given explicitly by \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). Each vertex has two neighbors, and those neighbors are not adjacent: for example, \(N(1)=\{2,4\}\), but \(24\notin E\). Thus no vertex is simplicial, so no first deletion is possible and the graph has no PEO. In particular, it would be wrong to say that \(1\) is simplicial merely because it has only two neighbors. The definition requires those neighbors to be adjacent to each other.

A second common error is to insert an edge between neighbors when deleting a vertex. That operation changes the graph; it is not the deletion used in a PEO. Here, at each step, the next graph is the induced subgraph on the vertices not yet deleted. The examples rely on checking exactly those surviving edges.

These definitions and deletion checks give a practical way to build and verify orderings. For a proposed sequence, inspect each vertex’s later neighbors and test every pair for adjacency. For a construction, record the current graph at each step and choose only a vertex whose current neighborhood is a clique. The chordal-graph characterization explains the broader connection between chordality and the existence of such orderings; it is important not to assume that result before establishing it.