Let $G$ be a chordal graph with $n$ vertices.
Then every maximal clique of $G$ that contains no simplicial vertex of $G$ is a separating set of $G$ .
Proof: (induction on $n$)
When $G = K_n$ , there is no separating set, but all the vertices are simplicial, so the statement holds. When $G\neq K_n$, let $Q$ be a maximal clique containing no simplicial vertex of $G$ . Every chordal graph that is not a complete graph has two nonadjacent simplicial vertices (this follows, for example, from Lemma). Let $u$ and $v$ be such vertices. Note that $Q$ cannot contain both $u$ and $v$ ; we may assume that $v \notin Q$ . Hence $Q$ is a maximal clique in $G − v$ .
If $Q$ contains no simplicial vertex of $G − v$ , then the induction hypothesis implies that $Q$ separates $G − v$ . All neighbors of $v$ in $G$ lie in one component of $G − v − Q$ , since $N (v)$ is a clique in $G − v$. Hence $Q$ is also a separating set in $G$ .
If $Q$ contains at least one simplicial vertex of $G − v$ , then all such vertices lie in $N (v)$ , since they are not simplicial in $G$ . Therefore $u \notin Q$ , and $Q$ separates $v$ from $u$ .
I'm confused with the bolded parts: $u,v$ are simplicial in $G$ and $v\in G$, but how is that because we defined $Q$ to be the maximal clique that contains no simplicial vertex of $G$?
Also, $N (v)$ is a clique in $G − v$, but we're talking about $G-v$, so we can't mention $N(v)$ in that context?
And also I don't understand the last sentence (If $Q$ contains at least one simplicial vertex...)
I would appreciate if someone would give a nice explanation of these things.
$u$ and $v$ are non-adjacent by definition, this is why that are not both in $Q$.
For the second difficulty, the notation is indeed improper: we should denote $N_G(x)$ or $N_{G-v}(x)$ for instance. Here, $N(v)$ is a clique in $G - v$ means: consider $N_{G}(v)$, which is a subset of vertices of $G$, because it does not contain $v$, it is also a subset of vertices of $G - v$, and as such is a clique in $G - v$.
Finally, if $x \in Q$ is simplicial in $G-v$, by assumption it is not simplicial in $G$, hence it has two nonadjacent neighbors $w_1$, $w_2$ in $G$. As all its neighbors in $G - v$ are pairwise adjacent, it must be that one of $w_1$, $w_2$ is $v$. Hence $x \in N_G(v)$. Because by assumption $u$ and $v$ are nonadjacent, this means $u \notin Q$.
Then, consider any neighbor $w$ of $N_G(v)$. $w$ and $x$ must be adjacent because $v$ is simplicial, hence $N_G(w)$ must contain $Q$ because $x$ is simplicial in $G-v$. By maximality of $Q$, $w \in Q$. That is $N_G(v) \subseteq Q$, hence $v$ is separated from all the other vertices of $G - Q$, in particular from $u$.