property of minimal triangulations

A graph is chordal if every cycle on four or more vertices contains a chord i.e. an edge between non-adjacent vertices of the cycle. A triangulation (or chordalization) of a graph $$G=(V,E)$$ is the addition of fill-in'' edges $$F$$ to $$G$$ such that the graph $$H = (V, E \cup F)$$ is chordal. A triangulation is minimal if, for every $$F' \subset F$$, $$(V, E \cup F')$$ is not chordal.

Is the following a known property of minimal triangulations? It seems highly plausible, but I have struggled to locate a proof in the literature.

• If $$H=(V,E \cup F)$$ is a minimal triangulation of a graph $$G$$, then every fill-in edge in $$F$$ is a chord of some cycle $$C$$ in the original graph $$G$$.

Informally, this says that the addition of fill-in edges cannot create completely new cycles, not present in the original graph, that in turn require extra fill-in edges.

I am aware that there is a deep literature on minimal triangulations linking them to (amongst other objects) minimal separators, but I have struggled to pin down a direct statement and proof of this intuitively reasonable claim. Can anybody help with a proof and/or reference? Thank you!

• It should follow from the fact that every fill-edge $uv$ is a subset $\{u,v\} \subseteq S$ of a minimal separator $S$ of the original graph. Commented Feb 15 at 13:09

As @Laakeri commented, the connection between triangulations and minimal separators can be used to show this property.

Based on the definitions:

• A subset $$S \subseteq V$$ is an $$a, b$$-separator of $$G$$ if $$a, b \in V$$ are in different components of $$G \setminus S$$.
• An $$a, b$$-separator $$S$$ is minimal if no proper subset of $$S$$ separates $$a$$ and $$b$$.
• A subset $$S$$ is a minimal separator of $$G$$ if $$S$$ is minimal $$a, b$$-separator for some $$a, b \in V$$.

And from the propositions:

• Graph $$H = (V, E \cup F)$$ is a minimal triangulation of $$G$$ if and only if $$H$$ can be obtained from $$G$$ by completing a maximal set of pairwise non-crossing minimal separators into cliques.
• Furthermore, every minimal separator in $$H$$ is also a minimal separator in $$G$$.

It immediately follows that:

• For every edge $$uv \in F$$ there exists a minimal separator $$S$$ of both $$H$$ and $$G$$ such that $$u, v \in S$$.

• To sum up, for every edge $$uv \in F$$, there exist some $$a, b \in V$$, such that $$a, u, b, v$$ are part of a cycle in $$G$$. As a result, the edge $$uv$$ is a cord of a cycle in $$G$$.

Lastly, a reference that contains proofs of the propositions:

• Claim 1: every fill-in edge $$\{u,v\}$$ is a subset of a minimal separator $$S$$ of the original graph $$G$$. Proof: first I show that $$\{u,v\}$$ is a subset of a minimal separator $$S$$ of the chordal graph $$H$$. The claim will then follow because every minimal separator of $$H$$ is a minimal separator of $$G$$ (see Lemma 5.1 of [1]). Continuing: $$H$$ is chordal so it can be represented as a tree decomposition in which the bags are exactly the maximal cliques of $$H$$. By Theorem 3.7 of [1], the minimal separators of a chordal graph $$H$$ are in bijection with the edges of the tree decomposition in the following sense: if $$S$$ is a minimal separator of $$H$$, then there exist two adjacent bags $$X$$ and $$Y$$ in the tree decomposition such that $$X \cap Y = S$$. So to complete the proof of the claim, we need to find two adjacent bags $$X, Y$$ such that $$\{u,v\}$$ is a subset of both of them. If this holds, we are done. If not, then the subtree of the tree decomposition induced by bags containing $$u$$, and the subtree induced by bags containing $$v$$, overlap in exactly one bag $$X$$. We replace $$X$$ with two adjacent bags $$(X \setminus \{u\})$$ and $$(X \setminus \{v\})$$. This is a tree decomposition for the chordal graph $$H'$$ obtained by deleting edge $$\{u,v\}$$ from $$H$$, and the new bags are in bijection with the maximal cliques of $$H'$$. Hence, $$H'$$ is a triangulation of the original graph $$G$$ with a subset of the original fill-in edges, yielding a contradiction on the assumption that $$H$$ was a minimal triangulation of $$H$$.
• Claim 2: If fill-in edge $$\{u,v\}$$ is part of a minimal separator $$S$$ of the original graph $$G$$, then it must be a chord of some cycle of the original graph $$G$$. Proof: $$G \setminus S$$ is a separator so splits what remains of $$G$$ into connected components $$C_1, C_2, ...$$. By minimality, $$G\setminus (S -u)$$ is not a separator, so in $$G$$ there must be an edge from $$C_1$$ to $$u$$, from $$C_2$$ to $$u$$, and so on. Symmetrically, there must be an edge from $$C_1$$ to $$v$$, from $$C_2$$ to $$v$$, and so on. Hence, we know that the edges $$\{p_1,u\}, \{q_1, v\}$$ exist, where $$p_1, q_1 \in C_1$$ and we know that the edges $$\{p_2, u\}, \{q_2, v\}$$ exist where $$p_2, q_2 \in C_2$$. In $$C_1$$ there is a (shortest) path from $$p_1$$ to $$q_1$$ and in $$C_2$$ there is a path from $$p_2$$ to $$q_2$$. These paths, together with the four named edges, form a cycle on at least 4 vertices, and $$\{u,v\}$$ is a chord of this cycle.
• Nice, just a small comment: In the explanation of Claim 2, you miss a subtlety of the definition of minimal separators: We define that $S$ is a minimal separator if there exists $a,b \in V(G) \setminus S$ so that $S$ is a minimal $a,b$-separator. This means that it does not hold necessarily for every component $C$ of $G \setminus S$ that $C$ is adjacent to every $u \in S$, but instead there exists two components $C_1,C_2$ so that $C_1$ and $C_2$ are adjacent to every $u \in S$. But two components is all you need for the argument to go through anyway. Commented Feb 21 at 23:19