<p>Chordal graphs can be <strong>defined</strong> as intersection graph of subtrees of any tree.  So the answer to your decision question is trivially YES.  On the construction side, for each subtree $T_v$ of bags (it's convenient and conventional to call the nodes of the tree as bags), you'll have a unique new vertex $v$, which is put into all bags of the $T_v$.  </p>

CC BY-SA 3.0
2014-03-08T12:10:37.120Z
Excuse me, but it's hard for me to understand your answer. Would you clarify how you construct a chordal graph from a tree?
Yoshio Okamoto
CC BY-SA 3.0
2014-03-07T22:51:46.907Z
2014-03-07T22:51:46.907Z
Yixin Cao
<p>If I understood your question correctly, you want to know whether every tree $T$ is the clique tree of a chordal graph $G$. In this case, the answer is yes.</p>

<p>To see this, take the family of subtrees being the set of vertices and the set of edges of $T$.</p>

<p>To see that the vertices of $T$ correspond to the maximal cliques of $G$, notice that for each node $C$ of $T$ there is a subtree $T_v$ corresponding to it, hence $v$ is a simplicial vertex on $G$ and cannot be adjacent to any other vertex non-incident in $C$.</p>

CC BY-SA 3.0
2014-03-07T20:57:56.740Z
2014-03-07T20:57:56.740Z
Vinicius dos Santos
<p>A graph $G$ is chordal if it is the intersection graph of subtrees of a tree $T$. In particular $T$ can be chosen such that each node of $T$ corresponds to a maximal clique of $G$ and the subtrees $T_v$ consist of precisely those maximal cliques in $G$ that contain $v$. $T$ is then called the clique tree of $G$. </p>

<p>Now my question is the following. </p>

<blockquote>
  <p>Is any tree can be represented as a clique tree of some chordal graph?</p>
</blockquote>

<p>Any counter example or hint of proof is welcome.</p>

<graph-theory>
Chordal graph and its clique tree
Dibyayan
# Chordal graph and its clique tree

(Asked by: username_0 on 2014-03-07)

A graph $G$ is chordal if it is the intersection graph of subtrees of a tree $T$. In particular $T$ can be chosen such that each node of $T$ corresponds to a maximal clique of $G$ and the subtrees $T\_v$ consist of precisely those maximal cliques in $G$ that contain $v$. $T$ is then called the clique tree of $G$.

Now my question is the following.

> Is any tree can be represented as a clique tree of some chordal graph?

Any counter example or hint of proof is welcome.

**Tags:** graph-theory


---

## 2 answers

### Answer by username_1 on 2014-03-07. Score: 4 | Accepted answer

Chordal graphs can be **defined** as intersection graph of subtrees of any tree. So the answer to your decision question is trivially YES. On the construction side, for each subtree $T\_v$ of bags (it's convenient and conventional to call the nodes of the tree as bags), you'll have a unique new vertex $v$, which is put into all bags of the $T\_v$.

> **Comments:**
> **username_2**: Excuse me, but it's hard for me to understand your answer. Would you clarify how you construct a chordal graph from a tree?  

---

### Answer by username_3 on 2014-03-07. Score: 2

If I understood your question correctly, you want to know whether every tree $T$ is the clique tree of a chordal graph $G$. In this case, the answer is yes.

To see this, take the family of subtrees being the set of vertices and the set of edges of $T$.

To see that the vertices of $T$ correspond to the maximal cliques of $G$, notice that for each node $C$ of $T$ there is a subtree $T\_v$ corresponding to it, hence $v$ is a simplicial vertex on $G$ and cannot be adjacent to any other vertex non-incident in $C$.


---

