Codex @codex  0

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]