\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Needs:
Vertex Separators
Needed by:
None.
Links:
Sheet PDF
Graph PDF

Chordal Graphs and Vertex Separators

Why

We characterize chordal graphs using vertex separators, and vice versa.1

Main Result

An undirected graph is chordal if and only if all minimal vertex separators are complete.
Let $G = (V, E)$ be an undirected graph.

First, suppose that all minimal vertex separators of $G$ are complete. Let $c$ be a cycle of length greater than 3. Let $v, w$ be nonconsecutive vertices in $c$. If $v$ and $w$ are adjacent in $G$, then $\set{v, w} \in E$ is a chord. If $v$ and $w$ are nonadjacent, then $vw$-separator exists.

The key insight is that there exists two non-consecutive vertices in the cycle that are also included in any $vw$-separator $T$. Split the cycle into the path from $v$ to $w$, call it $p_1$ and the path from $w$ to $v$, call it $p_2$. $T$ must include an interior point of $p_1$, call it $u_1$, otherwise $v$ and $w$ are connected. Similarly, $T$ must include an interior point of $p_2$, call it $u_2$. $u_1$ and $u_2$ are not consecutive in $c$, since they are distinct from $x$ and $y$.

Let $S$ be a minimal $vw$-separator. Let $s, t \in S$ be two non-consecutive vertices in the cycle different from $v$ and $w$ By assumption $S$ is complete, so $s$ and $t$ are adjacent in $G$.

Second, let $G = (V, E)$ be a chordal graph. Let $S$ be a minimal $vw$-separator. Let $C_v$ and $C_w$ be the connected components containing $v$ and $w$ of the subgraph induced by $V \setminus S$.

If $\nu m{S} = 1$, then $S$ is complete. Otherwise, let $x, y \in S$ by distinct. We want to show $\set{x, y} \in E$. The key insight is that $x$ is adjacent to vertices in $C_v$ and $C_w$. If there were no such vertex, $S \setminus \set{x}$ would be a $vw$-separator and $S$ would not be minimal. Similarly with $y$. Also, $\nu m{C_v}, \nu m{C_w} \geq 1$.

With these observations, there exists a path from $x$ to $y$ through $C_v$. Let $p_v = (x, v_1, \dots , v_k, y)$ be a path of shortest length with at least one interior vertex (so $k \geq 1$) from $x$ to $y$ using interior vertices in $v_1, \dots , v_k \in C_v$. Let $p_w = (y, w_1, \dots , w_l, x)$ be a path of shortest length with at least one interior vertex (so $l \geq 1$) from $y$ to $x$ using interior vertices $w_1, \dots , w_k \in C_w$. Use $p_v$ and $p_w$ to define the cycle $c = (x, v_1, \dots , v_k, y, w_1, \dots , w_l, x)$ which has length at least four. $G$ is chordal, so $c$ has a chord.

We argue that the chord of $c$ is $\set{x, y}$. Since $C_w$ and $C_V$ are different connected components (whose vertices are not included in $S$), there are no edges $\set{v_i, w_j}$ for $i = 1, \dots , k$ and $j = 1, \dots , l$. Since $p_v$ and $p_w$ are paths of shortest length, they have no chords. In particular, there is no edge $\set{v_i, v_j}$ for $\abs{i - j} > 1$ or $\set{v_i, x}$ for $i = 1, \dots , l$. Similarly, there is no edge $\set{w_i, w_j}$ for $\abs{i - j} > 1$ or $\set{w_i, y}$ for $i = 1, \dots , l$. The only remaining pair is $\set{x, y}$, and so it must be the chord.


  1. Future editions will expand and may include graphics. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view