2
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Laakeri
    Feb 15 at 13:09

2 Answers 2

4
$\begingroup$

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:

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Laakeri
    Feb 21 at 23:19
  • $\begingroup$ Ah, yes, thanks for pointing that out :-) $\endgroup$ Feb 22 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.