A question about chordal graphs.

123 Views Asked by At

I am working on a problem about Chordal graphs and I was wondering if a statement might be true: Suppose $G$ is Chordal and not a clique. Then there are two non-adjacent vertices $a,b$ and we get a minimal $a-b$-separator $S$. Since $G$ is chordal we know that $S$ is a clique. Want I would like to show is that for the connected component $A$ that contains $a$ there is a vertex $v\in A$ such that $S\subseteq \mathcal{N}(v)$. Similarly for the connected component that contains $B$ there is a vertex $w$ with the same property.

It's easy to see if $A$ only contains $a$ and $B$ only contains $b$. But as soon as I assume that the components contain more vertices I am a bit unsure and kinda stuck. Here is what I have so far: W.l.o.g. I can only focus on the component $A$ and try to find such a vertex.

I start by looking at the set $L:=\{v\in A \colon v\in\mathcal{N}(s) \text{ for }s\in S\}$ of all the neighbours of the vertices in the separator that are in $A$. Since $S$ is minimal I know that every vertex does have one. Thus, if $|L|=1$ we are done. So assume that $|L|>2$. Then either we find such a vertex or we know that there are two vertices $v,w\in L$ such that $\mathcal{N}(v)\cap S$ and $\mathcal{N}(w)\cap S$ are different in the sense that neither is contained in the other. We choose $v$ and $w$ as maximal with respect to the size of $\mathcal{N}(v)\cap S$ and $\mathcal{N}(w)\cap S$.

Now I claim that $v$ and $w$ can't be connected. Assume otherwise. Since $A\cup S$ is also chordal we find a perfect elimination ordering $\{v_1,\dots, v_n\}$ such that the neighbours of $v_i$ induced on the vertex set following $v_i$ form a clique. We know that we have to remove $v$ or $w$ before any vertex in $(\mathcal{N}(v)\cap S)\setminus (\mathcal{N}(w)\cap S)$ or $(\mathcal{N}(w)\cap S)\setminus (\mathcal{N}(v)\cap S)$, because otherwise we would violate the condition that the neighbourhood forms a clique in the following vertex set. This picture might help to understand what I mean:

But then $v$ and $w$ cannot be connected, because if we remove either one of them before any vertex in $(\mathcal{N}(v)\cap S)\setminus (\mathcal{N}(w)\cap S)$ or $(\mathcal{N}(w)\cap S)\setminus (\mathcal{N}(v)\cap S)$ would also contradict the the condition of the perfect elimination ordering. (Or I guess we use the cordiality, which seems a bit more straightforward :D)

For the next step I want to use that $A$ is connected. So there is a path from $v$ to $w$. Assume first that the path has length one, i.e. they have a common neighbour $u$ in $A$. Then I claim this violates the maximality of $v$ and $w$ with respect to the choice we made earlier. Because $A\cup S$ is still chordal we know that $u$ together with any common neighbour of $v$ and $w$ in $S$ is a cycle of length 4. Thus, since $v$ and $w$ are not connected, we have that $u$ is connected to every common neighbour in $S$. Now we can also pick a vertex from $(\mathcal{N}(v)\cap S)\setminus (\mathcal{N}(w)\cap S)$ and one from $(\mathcal{N}(w)\cap S)\setminus (\mathcal{N}(v)\cap S)$. This gives us a cycle of length 5 since $S$ is a clique. However, due to the cordiality and the choice of these vertices $u$ has to be connected to both these vertices. Thus, the existence of this $u$ violates the maximality of $v$ and $w$.

Lastly we have the case where $v$ and $w$ don't have a common neighbour in $A$. Here I am stuck. If I use that they are connected by a path of length at least 2 I cannot use the same argument as above. For every pair $z, z^\prime$ as above I now have a choice to connect it to either vertex on the path. So I think I cannot come to the same contradiction I used above. Also using the fact that there is path that contains $a$ and that $S$ is a minimal $a-b$-separator didn't bring me any more insight.

So my question is if the argument above makes any sense and if anyone has an idea or tipps on how to continue :D

Thank you and best regards!