![]() ![]() |
Proof:
Let M be the intersection multigraph of the family
(Tx/x For the other direction, we extend M to some multigraph M´ whose underlying graph is again chordal, but where k=m. This is simply done by repeatedly adding new vertices, and making them simply adjacent to the two endvertices of an edge xy where m(xy) < k(xy). Next we choose any representation of the underlying graph G´ of M´ having the property that all vertices of the tree correspond to cliques of G´. As mentioned, compare also the Weighted-Clique-graph Theorem, such a representation is always possible. It is easy to see that this is also a representation of M´. Finally, by deleting representatives of the added vertices, one surely gets a representation of M. |