The Chordal Graph Characterization by Perfect Elimination

Chordal Graphs and Elimination

A chord in a cycle is an edge joining two vertices that are not consecutive on the cycle. A cycle is induced if it has no chord. Chordal graphs are precisely the graphs in which every cycle of length at least four has a chord. Their structure can be recognized by repeatedly removing vertices whose remaining neighbors are all mutually adjacent. The key to proving this recognition method is showing that every nonempty chordal graph has at least one such vertex.

Throughout, graphs are finite and simple. For \(S\subseteq V(G)\), the induced subgraph \(G[S]\) has vertex set \(S\) and contains every edge of \(G\) with both endpoints in \(S\). A vertex \(v\) is simplicial if its neighborhood \(N(v)\) is a clique: every two distinct vertices in \(N(v)\) are adjacent.

The adjective “perfect” records that each vertex is simplicial at the moment it is removed: its remaining neighbors are exactly its later neighbors in the ordering. A graph with one vertex has a PEO, and the empty graph has the empty ordering. We will include both cases when proving the characterization.

The Simplicial-Vertex Lemma

We first prove a stronger fact that will supply simplicial vertices even when a chordal graph is not complete. A graph is complete if every two distinct vertices are adjacent.

Proof. We use induction on the number of vertices. If the graph has one vertex, it is complete. Assume the statement holds for chordal graphs with fewer than \(n\) vertices, and let \(G\) be chordal with \(n\) vertices.

First suppose \(G\) is disconnected. Each component is an induced subgraph of \(G\), and is chordal: an induced cycle in a component would also be an induced cycle in \(G\). Each component has fewer than \(n\) vertices, so the induction hypothesis gives it a simplicial vertex: if the component is complete, any of its vertices works; otherwise the hypothesis gives two. Choose simplicial vertices from two different components. They remain simplicial in \(G\), since there are no edges between components, and they are nonadjacent. Thus the lemma holds in this case.

Now suppose \(G\) is connected but not complete. Choose nonadjacent vertices \(a,b\). A set \(S\subseteq V(G)\setminus\{a,b\}\) separates \(a\) from \(b\) if deleting \(S\) leaves no path from \(a\) to \(b\). Such a set exists: deleting all vertices other than \(a,b\) separates them, since \(ab\notin E(G)\). Choose an inclusion-minimal separating set \(S\), meaning no proper subset of \(S\) separates \(a\) and \(b\). Let \(A\) and \(B\) be the vertex sets of the components of \(G-S\) containing \(a\) and \(b\), respectively. They are distinct, nonempty, and have no edges between them.

We claim that \(S\) is a clique. For any \(s\in S\), minimality means \(S\setminus\{s\}\) does not separate \(a\) and \(b\). There is therefore an \(a\)-to-\(b\) path in \(G-(S\setminus\{s\})\). This path must pass through \(s\), since \(S\) separates \(a\) and \(b\); it contains no other vertex of \(S\). The portion before \(s\) lies in the component \(A\), and the portion after \(s\) lies in \(B\). In particular, \(s\) has a neighbor in each of \(A\) and \(B\).

If distinct \(x,y\in S\) were nonadjacent, there would be an \(x\)-to-\(y\) path with interior in \(A\), and another with interior in \(B\): use the neighbors of \(x,y\) in that component and its connectedness. Choose a shortest such path in each of the induced subgraphs \(G[A\cup\{x,y\}]\) and \(G[B\cup\{x,y\}]\). Each path has length at least two, since \(xy\) is not an edge. A shortest path has no edge between nonconsecutive vertices of the path, since that edge would give a shorter path. The two paths together form a cycle of length at least four. It is induced: neither path has a chord, \(xy\) is absent, and there are no edges between \(A\) and \(B\). This contradicts chordality. Hence \(S\) is a clique.

Consider the induced subgraphs \(G[A\cup S]\) and \(G[B\cup S]\). Each is chordal and has fewer than \(n\) vertices, because the first omits the nonempty set \(B\), and the second omits \(A\). In \(G[A\cup S]\), if the graph is complete, choose any vertex of \(A\); it is simplicial there. If it is not complete, the induction hypothesis gives two nonadjacent simplicial vertices, at most one of which can belong to the clique \(S\). So in either case there is a simplicial vertex in \(A\). This vertex is simplicial in \(G\) as well, because vertices in \(A\) have no neighbors outside \(A\cup S\). Applying the same argument to \(G[B\cup S]\) gives a simplicial vertex in \(B\). These two vertices are nonadjacent, since there are no edges between \(A\) and \(B\). This completes the induction. \(\square\)

In particular, every nonempty chordal graph has a simplicial vertex: a complete graph has one, and the lemma supplies one when the graph is not complete. This conclusion also applies after vertices have been deleted. Indeed, every induced subgraph of a chordal graph is chordal, because any induced cycle in that subgraph would be induced in the original graph.

The Characterization

Proof. First suppose \(G\) is chordal. We prove by induction on \(n=|V(G)|\) that it has a PEO. If \(n=0\), use the empty ordering. If \(n>0\), the simplicial-vertex lemma gives a simplicial vertex \(v\). The graph \(G-v\) is an induced subgraph of \(G\), so it is chordal. By induction, \(G-v\) has a PEO, say \(v_2,\dots,v_n\). Put \(v\) first. Its later neighbors are all of \(N_G(v)\), a clique because \(v\) is simplicial. Each other vertex has the same later neighbors it had in the ordering of \(G-v\). Therefore \(v,v_2,\dots,v_n\) is a PEO.

Conversely, suppose \(G\) has a PEO \(v_1,\dots,v_n\). If \(G\) had an induced cycle of length at least four, choose the vertex \(v_i\) on that cycle with the smallest index. Both cycle neighbors of \(v_i\) occur later in the ordering. By the PEO condition they are adjacent. In a cycle of length at least four, those two neighbors are nonconsecutive on the cycle, so their edge is a chord. This contradicts that the cycle is induced. Thus \(G\) has no induced cycle of length at least four and is chordal. The argument also covers graphs with fewer than four vertices: they cannot contain such a cycle. \(\square\)

The forward proof gives an elimination procedure as well as an existence result: find a simplicial vertex, remove it, and repeat in the remaining induced subgraph. The lemma guarantees a choice at every nonempty stage. The reverse proof explains why the ordering condition is decisive: the earliest vertex on an induced cycle would have two later neighbors that the PEO forces to be adjacent.

Using the Characterization Carefully

A PEO is an ordering with a local condition checked at every position. To verify one, calculate the later-neighbor set for each vertex and confirm that every pair in each set is joined by an edge. To disprove that a particular ordering is a PEO, it is enough to find one vertex whose later neighbors are not a clique. But that does not by itself show the graph is not chordal: the third example has a failing ordering and also has a valid one.

To show a graph is not chordal, an induced cycle of length at least four is a direct certificate. To show it is chordal using the characterization, a PEO is a certificate. The simplicial-vertex lemma explains why the elimination process succeeds in every chordal graph, including disconnected graphs: each component can be handled through the induced subgraphs formed during elimination, and isolated vertices are simplicial because their neighborhood is empty.

Common mistake. It is not enough for every vertex to have a small number of later neighbors; those neighbors must be pairwise adjacent. In the path example, vertex \(2\) has exactly two later neighbors in the ordering \(2,1,3\), but \(1\) and \(3\) are not adjacent. The condition fails. Reordering to \(1,3,2\) changes the later-neighbor sets and makes each a clique. Always test adjacency within each set, not just its size.