Chordal Graph Checker

Pseudocode

Testing chordality directly, by hunting for a long chordless cycle, is expensive. The standard route is indirect: find a candidate perfect elimination ordering, then verify it.

// Step 1: maximum cardinality search
weight[v] = 0 for all v; order = []
repeat V times:
    pick unnumbered v with the largest weight
    order.prepend(v)
    for each unnumbered neighbor n of v: weight[n]++

// Step 2: verify it is a perfect elimination ordering
for each v in order, at position i:
    later = neighbors of v appearing after i
    if later is empty: continue
    w = the earliest vertex in later
    if any u in later is not adjacent to w:
        return NOT chordal
return chordal

A perfect elimination ordering is one where each vertex, together with its later neighbours, forms a clique. A graph is chordal exactly when such an ordering exists. Maximum cardinality search always produces one if the graph is chordal, so the verification step is what turns a heuristic ordering into a proof, and it is also what detects the failure when no such ordering exists.

Worked example, step by step

Test a four-cycle for chordality, then add one chord and test again.

Example graph: First the 4-cycle A-B, B-C, C-D, D-A. Then the same graph with the chord A-C added.

1. Run MCS on the 4-cycle. Maximum cardinality search produces the ordering D, C, B, A.
2. Verify D. D appears first. Its neighbours later in the ordering are C and A. The earliest of those is C, so the check asks whether A is adjacent to C. In the plain 4-cycle it is not.
3. Reject. The ordering is not a perfect elimination ordering, and since MCS would have found one had the graph been chordal, the 4-cycle is not chordal. This is right: A-B-C-D-A is a cycle of length 4 with no chord.
4. Add the chord A-C and retest. MCS again gives D, C, B, A. Verifying D, its later neighbours are C and A, and now A is adjacent to C, so the check passes. Verifying C, its later neighbours are B and A, which are not adjacent to each other, but the test only requires the others to be adjacent to the earliest, which is B... and A-B is an edge, so it passes. Every remaining vertex has at most one later neighbour and passes trivially.

The plain 4-cycle is not chordal; adding the single chord A-C makes it chordal. This is the definition made concrete: a graph is chordal when every cycle of four or more vertices has an edge joining two non-consecutive vertices of that cycle. The 4-cycle is the smallest possible counterexample, which is why it is the standard test case.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V + E)

Maximum cardinality search runs in O(V + E) when implemented with buckets of vertices by weight, so that selecting the maximum and incrementing neighbours are both amortised constant. The verification pass examines each vertex once and each of its later neighbours once, which totals O(V + E) provided adjacency queries are constant time via a hash set. So the whole test is linear, which is a genuinely surprising result: the naive approach of enumerating cycles and checking each for a chord is exponential, and even a smarter cycle-based method would be far worse. Lexicographic BFS is an alternative to MCS with the same bound.

When to use Chordality Check, and when not to

Chordality is usually a gateway: once a graph is known to be chordal, several NP-hard problems become linear on it.

Common pitfalls

• Skipping the verification step. MCS produces an ordering for any graph, chordal or not. Only the verification pass distinguishes the two. Treating the MCS output as proof of chordality accepts every graph.
• Misreading the definition as "every cycle has a chord". The condition applies only to cycles of length 4 or more. Triangles have no non-consecutive vertex pairs and so trivially satisfy it. Every triangle-only graph is chordal.
• Checking all pairs of later neighbours. The verification only needs to compare each later neighbour against the earliest of them, not against every other. Checking all pairs is correct but turns a linear algorithm into a quadratic one.
• Assuming chordal means dense or tree-like. Trees are chordal because they have no cycles at all, and complete graphs are chordal because every possible chord is present. Chordality is not a measure of density and cuts across it.
• Forgetting to test every connected component. A graph is chordal only if all its components are. MCS naturally spans components when implemented over all vertices, but a per-component implementation must iterate over all of them.

Frequently asked questions

What is a chordal graph?

A chordal graph is one in which every cycle of four or more vertices has a chord, meaning an edge joining two vertices that are not consecutive on that cycle. Equivalently, it has no induced cycle longer than a triangle. Trees, complete graphs and interval graphs are all chordal; the plain 4-cycle is the smallest graph that is not.

How do you check if a graph is chordal?

Run maximum cardinality search to produce a candidate perfect elimination ordering, then verify it: for each vertex, its neighbours that come later in the ordering must all be adjacent to the earliest among them. If the verification passes the graph is chordal; if it fails, no perfect elimination ordering exists and the graph is not. The whole test is O(V + E).

What is a perfect elimination ordering?

An ordering of the vertices in which every vertex, taken together with its neighbours that appear later, forms a clique. A graph has such an ordering exactly when it is chordal, which is why finding and verifying one is the standard chordality test.

Why do chordal graphs matter?

Because several problems that are NP-hard in general become linear on them. Maximum clique, graph colouring, maximum independent set and minimum clique cover are all solvable in O(V + E) on a chordal graph using the elimination ordering. Chordal graphs are also exactly the graphs admitting a tree decomposition into cliques, which underpins treewidth-based algorithms.

Are all trees chordal?

Yes, trivially. Chordality only constrains cycles of length 4 or more, and a tree has no cycles at all, so the condition is vacuously satisfied. At the other extreme, complete graphs are chordal too, since every possible chord is already present.