Logo

[BG81]: A chordal graph G is the intersection graph of subtrees of some tree T if and only if T is contractible to some maximum spanning tree of the clique multigraph CM(G) of G.

The proof of the Theorem uses the following characterization of chordal graphs: We say a spanning tree T of CM(G) has the inclusion-property if C0 Ct ... C0 C2 C0 C1 for every path C0 ,C1,...,Ct in T.

Let T be a maximal spanning tree of CM(G). Then G is chordal if and only if T has the inclusion-property.

Proof: The proof is by induction on the vertex number and uses the well-known fact that every chordal graph has some so-called simplicial vertex---a vertex with complete neighborhood. The details are left to the reader.

Proof of the [BG81]-Theorem: Let T be a maximum spanning tree of CM(G). We define Tx := T[{CV(T)/ xC}] for every vertex x of G. Since T has the inclusion-property by the Proposition, each Tx is connected.

If S is contractible to T, then this representation can be extended to some representation by subtrees of S in an obvious way.

Conversely, assume G is the intersection graph of subtrees (Tx/ xV(G)) of some tree T. We may assume that T is a clique tree, i.e. the graphs a* are distinct cliques of G. In other words, T is a spanning tree of CM(G). If T were not maximum, then, by the Proposition, the inclusion property would be violated. Then C0 Ci would not include C0 Ct for some Ci lying between C0 and Ct on T. Then there were some vertex x occuring in C0 and Ct, but not in Ci, a contradiction to Tx being connected.


Erich Prisner
made on January 12, 1999