Graph Theory: Connectivity of digraphs

Question

I was wondering if someone could help me understand this proof that my professor gave us:

I get lost just after he defines the components of G - xy - S. For example I can't really see how G[x] must have x and G[y] must have y. Even if I skip this detail I don't understand how the rest of the proof flows.

Answer 1

We know that $G-S$ is strongly connected, but that $G-S-xy$ is no longer strongly connected. Thus, $G-S-xy$ has 2 strongly connected components and there is no other edge from the component containing $x$ into the component containing $y$. Denote $X$ the set of vertices of the component of $G-S-xy$ containing $x$, and denote $Y$ the set of vertices of the component of $G-S-xy$ containing $y$. Then $V(G)=X\cup Y\cup S$ (there was a typo in the proof at this point) an these unions are disjoint.

If $|X|\geq 2$, we notice that $S\cup\{x\}$ is a vertex cut of $G$ : if let $x'$ be another vertex (other than $x$) in $X$. Then any path from $x'$ to vertices of $Y$ must go through either $S$ or through $x$, as $xy$ is the only edge between $X$ and $Y$. Similarly, if $|Y|\geq 2$, then $S\cup\{y\}$ is a vertex cut of $G$. In both cases, we have found a vertex cut of $G$ of size $|S|+1=\kappa(G-xy)+1$.

The only other case to verify is when $|X|=|Y|=1$. Then $|S|=n(G)-|X|-|Y|=n(G)-2$, in which case $\kappa(G)$ must be $n(G)-1$ by the inequality from the beginning of the proof. Thus, to disconnect the graph, we must remove all vertices (except one) : the graph $G$ must be complete. We can disconnect $G-xy$ by removing all vertices except $x,y$ : this vertex cut has size $n(G)-2$.

Answer 2

So for the G - xy - S bit, we started the sentence with if k(G - xy) < k(G), so we are assuming that the removal of the edge xy strictly reduces the size of the cut needed, so therefore removing xy is part k(G).

This means that the cut of G-xy will always be one fewer than the cut of G (which is basically the proof), but it also means that the edges x and y must be disconnected in the cut S, since otherwise removing it in k(G) would not be the most efficient cut. Therefore we have 2 subgraphs of G, one that contains x and one that contains y.

It seems like the next bit adding a vertex x of y, respectively, creates a vertex cut in G, is wrongly worded? Adding a vertex doesn't make a cut, but removing the vertex will do, so I think this is a mistake in the solution. If you take it to mean removing a vertex x of y, respectively, creates a vertex cut in G, it makes much more sense.

The next bit is also weirdly worded. Hence doesn't make sense, but I think the tutor is trying to prove the edge cases, since the previous but assumed that |X| and |Y| were greater than or equal to 2. So here they instead mean now assuming |X| and |Y| equal to 1....

I find it makes this easier if you draw out some example graphs when working through these proofs, you can't use them as actual proof but it helps with the intuition.