Separators in a graph

Question

Let $G$ be a graph with vertices $a$ and $b$ and let $X \subseteq V(G) \setminus \{a, b\}$ be an $ab$ separator. Let $C_a, C_b$ be the components containing $a$ and $b$ respectively in $G - X$.

Let $X'$ be another separator with $C'_a, C'_b$ defined similarly. We need to show that both $$Y_a = (X \cap C'_a) \cup (X \cap X') \cup (X' \cap C_a)$$ $$Y_b = (X \cap C'_b) \cup (X \cap X') \cup (X' \cap C_b)$$

are separators of $G$. This seems pretty obvious from this diagram:

Although, I haven't been able to prove it formally. Also, are these separators minimal if $X, X'$ are minimal?

Answer 1

To show that $Y_a$ is a separator, consider an arbitrary path from $a$ to $b$.

Let $v$ be the first vertex of $X \cup X'$ we encounter along the path (starting from $a$). There are three cases:

1. $v \in X$, but $v \notin X'$. In this case, since we haven't reached $X'$ yet, we must still be in $C_a'$. Therefore $v \in X \cap C_a' \subseteq Y_a$.
2. $v \in X'$, but $v \notin X$. In this case, since we haven't reached $X$ yet, we must still be in $C_a$. Therefore $v \in X' \cap C_a \subseteq Y_a$.
3. $v \in X \cap X'$. We've included $X \cap X'$ in its entirety in $Y_a$, therefore $v \in Y_a$ yet again.

So either way, our path contains a vertex of $Y_a$, and we are done. (The set $Y_b$ is a separator by the same argument, if we switch the roles of $a$ and $b$.)

For an example where neither $Y_a$ nor $Y_b$ are minimal, even though both $X$ and $X'$ are, consider the graph below, with $X$ and $X'$ circled in red and blue.