Chordal Graphs Explained

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

What Is a Chordal Graph?

A chordal graph, also called a triangulated graph, is a graph in which every cycle of four or more vertices has a chord. A chord is an edge that joins two vertices of the cycle that are not next to each other along it. Put another way, a chordal graph contains no induced cycle of length four or more: every long cycle is broken up into triangles by shorter edges.

The definition sounds narrow, but many graphs you already know are chordal: trees, complete graphs, and interval graphs are all chordal. The figure below shows the smallest interesting case, a four-vertex cycle, in both its non-chordal and chordal forms.

Chords and Induced Cycles

The word doing the heavy lifting is induced. A cycle is induced when the only edges among its vertices are the cycle edges themselves. The moment a chord appears, the long cycle is no longer induced: it has been triangulated.

So the two definitions are the same statement seen from two angles:

• Every cycle of length ≥ 4 has a chord, or equivalently
• The graph has no induced cycle of length ≥ 4 (no induced C₄, C₅, and so on).

Triangles, being length-3 cycles, are always allowed and never need a chord. This is why chordal graphs feel like they are "built from triangles."

Simplicial Vertices and Elimination Orderings

The real power of chordal graphs comes from a structural theorem. First, two definitions.

• A vertex is simplicial if its neighbours form a clique, that is, they are all pairwise adjacent.
• A perfect elimination ordering (PEO) is an ordering v₁, v₂, …, vₙ of the vertices such that each vₚ is simplicial in the graph that remains after removing v₁ through vₚ₋₁.

The Fulkerson-Gross theorem ties it all together:

A graph is chordal if and only if it has a perfect elimination ordering. Moreover, every chordal graph has at least one simplicial vertex, so you can always start peeling one off.

This is the engine behind every efficient algorithm on chordal graphs. Once you have a PEO, you can process the vertices in that order and solve problems greedily, because at each step the vertex's remaining neighbours form a clique with no surprises.

Recognizing a Chordal Graph

Given a graph, how do you tell if it is chordal? You could hunt for induced cycles, but that is slow. The elegant route uses the PEO characterization and runs in linear time, O(V + E).

1. Run a lexicographic breadth-first search (Lex-BFS) or a maximum cardinality search. Both produce a vertex ordering by always visiting next the vertex with the most already-visited neighbours.
2. Reverse that ordering. If the graph is chordal, the reverse is guaranteed to be a perfect elimination ordering.
3. Verify that the candidate really is a PEO. If it is, the graph is chordal; if the check fails, it is not.

The search relies on breadth-first search, adapted so that ties are broken by lexicographic labels. The verification step is the part worth seeing in code.

Verifying an Ordering in Python

Here is the core check: given a graph as an adjacency set and a candidate ordering, decide whether it is a perfect elimination ordering. For each vertex, its later neighbours must all be adjacent to the earliest of them.

def is_perfect_elimination_order(graph, order):
    pos = {v: i for i, v in enumerate(order)}

    for v in order:
        # Neighbours of v that come later in the ordering.
        later = [u for u in graph[v] if pos[u] > pos[v]]
        if len(later) <= 1:
            continue

        # v is simplicial here iff those later neighbours form a clique.
        # It is enough to check they are all adjacent to the earliest one, w.
        w = min(later, key=lambda u: pos[u])
        for u in later:
            if u != w and u not in graph[w]:
                return False   # w and u follow v but are not adjacent

    return True

If this returns True for the reversed Lex-BFS ordering, the graph is chordal. The same PEO is then reused to solve the hard problems below.

Why Chordal Graphs Matter

Chordal graphs are perfect graphs, a class where the chromatic number always equals the size of the largest clique. That structure collapses several famously hard problems into easy ones. Given a perfect elimination ordering, each of these runs in linear time.

There is one more gem. A graph is chordal exactly when it has a clique tree, a tree decomposition whose bags are the maximal cliques. That connects chordal graphs to treewidth: the treewidth of any graph equals the smallest possible maximum clique size, minus one, over all its chordal completions. For where this class fits among the wider landscape, see the applications of graph theory and the study roadmap.

Real-World Applications

• Sparse matrix solvers: Gaussian elimination fills in zeros as it runs, and minimizing that fill-in is exactly the problem of adding chords to make a graph chordal, a chordal completion.
• Compilers: register allocation on modern SSA-form code becomes chordal graph coloring, which is why it can be solved optimally and quickly.
• Probabilistic models: the junction tree algorithm for Bayesian networks triangulates the graph, that is, makes it chordal, then works on its clique tree.
• Bioinformatics and scheduling: interval graphs, a chordal subclass, model overlapping intervals such as gene segments or time slots.