Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
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$.
