# Chordal graph and its clique tree

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.

-

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

-
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 Mar 8 '14 at 12:10

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

-