<p>As @Laakeri commented, the connection between triangulations and minimal separators can be used to show this property.</p>
<p>Based on the definitions:</p>
<ul>
<li>A subset <span class="math-container">$S \subseteq V$</span> is an <em><span class="math-container">$a, b$</span>-separator</em> of <span class="math-container">$G$</span> if <span class="math-container">$a, b \in V$</span> are in different components of <span class="math-container">$G \setminus S$</span>.</li>
<li>An <span class="math-container">$a, b$</span>-separator <span class="math-container">$S$</span> is <em>minimal</em> if no proper subset of <span class="math-container">$S$</span> separates <span class="math-container">$a$</span> and <span class="math-container">$b$</span>.</li>
<li>A subset <span class="math-container">$S$</span> is a <em>minimal separator</em> of <span class="math-container">$G$</span> if <span class="math-container">$S$</span> is minimal <span class="math-container">$a, b$</span>-separator for some <span class="math-container">$a, b \in V$</span>.</li>
</ul>
<p>And from the propositions:</p>
<ul>
<li>Graph <span class="math-container">$H = (V, E \cup F)$</span> is a minimal triangulation of <span class="math-container">$G$</span> if and only if <span class="math-container">$H$</span> can be obtained from <span class="math-container">$G$</span> by completing a maximal set of pairwise non-crossing minimal separators into cliques.</li>
<li>Furthermore, every minimal separator in <span class="math-container">$H$</span> is also a minimal separator in <span class="math-container">$G$</span>.</li>
</ul>
<p>It immediately follows that:</p>
<ul>
<li><p>For every edge <span class="math-container">$uv \in F$</span> there exists a minimal separator <span class="math-container">$S$</span> of both <span class="math-container">$H$</span> and <span class="math-container">$G$</span> such that <span class="math-container">$u, v \in S$</span>.</p>
</li>
<li><p>To sum up, for every edge <span class="math-container">$uv \in F$</span>, there exist some <span class="math-container">$a, b \in V$</span>, such that <span class="math-container">$a, u, b, v$</span> are part of a cycle in <span class="math-container">$G$</span>. As a result, the edge <span class="math-container">$uv$</span> is a cord of a cycle in <span class="math-container">$G$</span>.</p>
</li>
</ul>
<p>Lastly, a reference that contains proofs of the propositions:</p>
<ul>
<li>Section 4: Minimal separators and their connection to triangulations in <em>Andreas Parra and Petra Scheffler: Characterizations and algorithmic applications of chordal graph embeddings.</em>
<a href="https://www.sciencedirect.com/science/article/pii/S0166218X97000413" rel="noreferrer">https://www.sciencedirect.com/science/article/pii/S0166218X97000413</a></li>
</ul>

CC BY-SA 4.0
2024-02-16T12:41:46.570Z
2024-02-16T12:41:46.570Z
Marko Lalovic
<p>I often wondered about this question so I appreciate the comments and answers of Laakeri and Marko.</p>
<p>I don't know if it helps anybody but as someone who is not an expert on minimal separators I attempted to construct a proof, leveraging lemmas and theorems from the paper [1] &quot;Minimal triangulations of graphs: A survey&quot; by Heggenes (Discrete Mathematics, Volume 306, Issue 3, 2006,
Pages 297-317) as a black box, but also supplementing some of the concepts with a few more details.</p>
<ul>
<li><p>Claim 1: every fill-in edge <span class="math-container">$\{u,v\}$</span> is a subset of a minimal separator <span class="math-container">$S$</span> of the original graph <span class="math-container">$G$</span>. Proof: first I show that <span class="math-container">$\{u,v\}$</span> is a subset of a minimal separator <span class="math-container">$S$</span> of the chordal graph <span class="math-container">$H$</span>. The claim will then follow because every minimal separator of <span class="math-container">$H$</span> is a minimal separator of <span class="math-container">$G$</span> (see Lemma 5.1 of [1]). Continuing: <span class="math-container">$H$</span> is chordal so it can be represented as a tree decomposition in which the bags are exactly the maximal cliques of <span class="math-container">$H$</span>. By Theorem 3.7 of [1], the minimal separators of a chordal graph <span class="math-container">$H$</span> are in bijection with the edges of the tree decomposition in the following sense: if <span class="math-container">$S$</span> is a minimal separator of <span class="math-container">$H$</span>, then there exist two adjacent bags <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> in the tree decomposition such that <span class="math-container">$X \cap Y = S$</span>. So to complete the proof of the claim, we need to find two adjacent bags <span class="math-container">$X, Y$</span> such that <span class="math-container">$\{u,v\}$</span> 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 <span class="math-container">$u$</span>, and the subtree induced by bags containing <span class="math-container">$v$</span>, overlap in exactly one bag <span class="math-container">$X$</span>. We replace <span class="math-container">$X$</span> with two adjacent bags <span class="math-container">$(X \setminus \{u\})$</span> and <span class="math-container">$(X \setminus \{v\})$</span>. This is a tree decomposition for the chordal graph <span class="math-container">$H'$</span> obtained by deleting edge <span class="math-container">$\{u,v\}$</span> from <span class="math-container">$H$</span>, and the new bags are in bijection with the maximal cliques of <span class="math-container">$H'$</span>. Hence, <span class="math-container">$H'$</span> is a triangulation of the original graph <span class="math-container">$G$</span> with a subset of the original fill-in edges, yielding a contradiction on the assumption that <span class="math-container">$H$</span> was a minimal triangulation of <span class="math-container">$H$</span>.</p>
</li>
<li><p>Claim 2: If fill-in edge <span class="math-container">$\{u,v\}$</span> is part of a minimal separator <span class="math-container">$S$</span> of the original graph <span class="math-container">$G$</span>, then it must be a chord of some cycle of the original graph <span class="math-container">$G$</span>. Proof: <span class="math-container">$G \setminus S$</span> is a separator so splits what remains of <span class="math-container">$G$</span> into connected components <span class="math-container">$C_1, C_2, ...$</span>. By minimality, <span class="math-container">$G\setminus (S -u)$</span> is not a separator, so in <span class="math-container">$G$</span> there must be an edge from <span class="math-container">$C_1$</span> to <span class="math-container">$u$</span>, from <span class="math-container">$C_2$</span> to <span class="math-container">$u$</span>, and so on. Symmetrically, there must be an edge from <span class="math-container">$C_1$</span> to <span class="math-container">$v$</span>, from <span class="math-container">$C_2$</span> to <span class="math-container">$v$</span>, and so on. Hence, we know that the edges <span class="math-container">$\{p_1,u\}, \{q_1, v\}$</span> exist, where <span class="math-container">$p_1, q_1 \in C_1$</span> and we know that the edges <span class="math-container">$\{p_2, u\}, \{q_2, v\}$</span> exist where <span class="math-container">$p_2, q_2 \in C_2$</span>. In <span class="math-container">$C_1$</span> there is a (shortest) path from <span class="math-container">$p_1$</span> to <span class="math-container">$q_1$</span> and in <span class="math-container">$C_2$</span> there is a path from <span class="math-container">$p_2$</span> to <span class="math-container">$q_2$</span>. These paths, together with the four named edges, form a cycle on at least 4 vertices, and <span class="math-container">$\{u,v\}$</span> is a chord of this cycle.</p>
</li>
</ul>

CC BY-SA 4.0
2024-02-21T23:19:13.567Z
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.
Laakeri
CC BY-SA 4.0
2024-02-22T12:58:18.873Z
Ah, yes, thanks for pointing that out :-)
steven kelk
CC BY-SA 4.0
2024-02-20T07:28:41.737Z
2024-02-20T17:45:08.637Z
2024-02-20T17:45:08.637Z
steven kelk
<p>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 <span class="math-container">$G=(V,E)$</span> is the addition of ``fill-in'' edges <span class="math-container">$F$</span> to <span class="math-container">$G$</span> such that the graph <span class="math-container">$H = (V, E \cup F)$</span> is chordal. A triangulation is minimal if, for every <span class="math-container">$F' \subset F$</span>, <span class="math-container">$(V, E \cup F')$</span> is not chordal.</p>
<p>Is the following a known property of minimal triangulations? It seems highly plausible, but I have struggled to locate a proof in the literature.</p>
<ul>
<li>If <span class="math-container">$H=(V,E \cup F)$</span> is a minimal triangulation of a graph <span class="math-container">$G$</span>, then every fill-in edge in <span class="math-container">$F$</span> is a chord of some cycle <span class="math-container">$C$</span> in the <strong>original</strong> graph <span class="math-container">$G$</span>.</li>
</ul>
<p>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.</p>
<p>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!</p>

CC BY-SA 4.0
2024-02-15T13:09:21.243Z
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.
Laakeri
<graph-theory><triangulation>
property of minimal triangulations
CuriousChordalizer
# property of minimal triangulations

(Asked by: username_0 on 2024-02-15)

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!

**Tags:** graph-theory, triangulation
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2024-02-16. Score: 5

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:

* Section 4: Minimal separators and their connection to triangulations in *Andreas Parra and Petra Scheffler: Characterizations and algorithmic applications of chordal graph embeddings.*
  <https://www.sciencedirect.com/science/article/pii/S0166218X97000413>


---

### Answer by username_3 on 2024-02-20. Score: 0

I often wondered about this question so I appreciate the comments and answers of Laakeri and Marko.

I don't know if it helps anybody but as someone who is not an expert on minimal separators I attempted to construct a proof, leveraging lemmas and theorems from the paper [1] "Minimal triangulations of graphs: A survey" by Heggenes (Discrete Mathematics, Volume 306, Issue 3, 2006,
Pages 297-317) as a black box, but also supplementing some of the concepts with a few more details.

* 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.

> **Comments:**
> **username_1**: 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.  
> **username_3**: Ah, yes, thanks for pointing that out :-)  

---

