Construction for Chordal Graphs by Adding 3-cliques

52 Views Asked by At

Let $G=(V, E)$ be an undirected graph where $V$ is the set of vertices and $E = \emptyset$. $G$ is clearly chordal since it has no cycles. We are given a function $f(u,v,w,G)$ who takes as input $G$ and $u,v,w \in V$($u$, $v$ and $w$ are distinct vertices). It returns a new graph $G'=(V,E \cup U)$ where $U = \{ pq| pq \notin E,p \in \{ u,v,w\},q \in \{ u,v,w\}, p \neq q\}$. The chosen vertices $u,v,w$ are arbitrary. Is there a formal proof that $f$ preserves chordality? Does adding 3-cliques to a chordal graph preserve chordality?

1

There are 1 best solutions below

0
On BEST ANSWER

The function $f$ doesn't preserve chordality. I've included a picture of a graph which can be constructed by $4$ applications of $f$, which create the $4$ triangles. There is a clear chordless $4$ cycle in the center of the graph. This contradicts the idea that $f$ preserves chordality. Nonchordal example graph