Logo
[Mc91]: A multigraph is chordal if and only if its underlying graph is chordal and it fulfills the mk condition.

Proof: Let M be the intersection multigraph of the family (Tx/xV) of subtrees of some given tree T. Other than for ordinary intersection graphs, we can not require a* to be a clique (of the underlying graph G of M) for every vertex a of T. But some of them are, and every clique of G must be such a a*, by the Helly property. Therefore, if two vertices lie in k(xy) common cliques, then the corresponding subtrees T_x and T_y both contain at least k(xy) common vertices, thus m(xy)k(xy).

For the other direction, we extend M to some multigraph 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 of having the property that all vertices of the tree correspond to cliques of . 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 .

Finally, by deleting representatives of the added vertices, one surely gets a representation of M.



Erich Prisner
made on January 12, 1999