![]() |
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.
![]() |
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[{C 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/
x |