= Chordal graph
{wiki}
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\}$.
\Image[/chordal-perfect-elimination-square-cliques.png]
{title=An <induced cycle> loses its obstruction when one diagonal is added; the resulting <maximal cliques> form a <junction tree>}
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>.<An Introduction to Chordal Graphs and Clique Trees by Jean R. S. Blair and others>[§3.1–3.2]{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|\leq3|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 have
$$
p(x_a,x_b,x_c,x_d)=Z^{-1}\psi_{abc}(x_a,x_b,x_c)\psi_{acd}(x_a,x_c,x_d),
$$
where the two nonnegative <clique potentials> have a positive <normalizing constant> $Z$. Eliminating $x_b$ produces the two-variable <junction-tree sum-product message>
$$
m(x_a,x_c)=\sum_{x_b}\psi_{abc}(x_a,x_b,x_c),\qquad Z=\sum_{x_a,x_c,x_d}m(x_a,x_c)\psi_{acd}(x_a,x_c,x_d).
$$
The 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.<Recitation 8: Junction Trees by Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science>[§1; §6]{ref}
Back to article page
