intersection graph of tree $T$

337 Views Asked by At

Let $T=(V,E)$ be a tree and $S=(T_v), \; v \in V$ be a family of subtree's

The graph $G$ that has the sets $T_v$ as vertices and edges $(v,w)$ if and only if $T_v,T_w $ have a vertex in common

Prove that the intersection graph is chordal

In a chordal graph, every circle of length $\ge 4$ has a chord.

If $T_1....T_m$ are trees in a circle then $T_i, T_j$ have a vertex in common for some $1 \lt i,j \lt m \; m\neq j$

Would appreciate any help

1

There are 1 best solutions below

0
On

Suppose that an intersection graph $G$ of a tree $T$ has a cycle of length at least 4. Consider the corresponding family of nonempty subtrees $T_1, \ldots, T_k$ such that subtrees $(T_1,T_k)$ and $(T_i, T_{i+1})$ where $1 \leq i \leq k-1$ intersect and any other pair of subtrees don't intersect.

The subtree $T_1$ cannot be equal to the tree $T$, otherwise, the subtree $T_3$ must be empty and cannot intersect with any other subtree. Let $Z_1,\ldots, Z_m$ be the connected components of the forest $T/T_1$. The tree $T_3$ has no common vertices with $T_1$, that's why it belongs to some component $Z_i$. Suppose that the component $Z_i$ connected with the subtree $T_1$ by the edge $e_i$. This edge belongs to the subtree $T_2$ since it intersects with both subtrees $T_1$ and $T_3$. Since $e_i$ belongs to $T_2$, it does not belong to the subtrees $T_4, \ldots, T_k$. Every tree $T_l (4 \leq l \leq k)$ does not contain $e_i$ and intersects with the tree $T_{l-1}$, that's why it also belongs to $Z_i$. So the tree $T_k$ belongs to $Z_i$, but it does not contain $e_i$ and doesn't intersect with $T_1$.

We have a contradiction, that's why an intersection graph of a tree cannot be chordal.