Proving an st-cut is contained in a set containing at least one edge from all st-paths

Question

Let $G = (V, E)$ be a graph, let $s, t$ be vertices of $G$, and suppose each edge $e$ has a nonnegative weight $c_e$. Observe that an st-cut $\delta(U)$ intersects every $st$-path.

Suppose $S$ is a set of edges that contains at least one edge from every $st$-path. Show that there exists an $st$-cut $\delta(U)$ that is contained in the edges of $S$.

I've tried a few different ways to approach this problem, but I'm a neophyte when it comes to graph theory. How would I solve this problem and do you have any tips for what kind of mentality I should be using when solving problems similar to it?

Answer 1

A lot of the time (especially in graph theory, which is a very algorithm-based field) "show that there exists" statements involve describing a way to find the thing in question. So, when we see the words

Show that there exists an $s,t$-cut $\delta(U)$ that is contained in the edges of $S$

we should try to explain how to find a vertex set $U$, in terms of $S$, such that $\delta(U)$ has the property we want.

(A good first step to figuring out what $U$ should be is to try some examples.)

---

The correct description of $U$, in terms of $S$, is "let $U$ be the set containing $s$, and all vertices that can be reached from $s$ without taking an edge from $S$".

Or, to put it differently, "let $G'$ be the graph obtained from $G$ by deleting all vertices in $S$, and let $U$ be (the vertex set of) the connected component of $G'$ containing $s$".

Why is this the right choice? Well, we think about what vertices we are forced to add to $U$, if we want $\delta(U)$ to be an $s,t$-cut contained in $S$.

• We are forced to take $s \in U$, because this either is the definition of an $s,t$-cut or follows from it directly, depending what that definition actually is.
• Whenever $v \in U$, and $vw$ is an edge of $G$ not in $S$, we are forced to have $w \in U$. Otherwise, if $v \in U$ and $w \notin U$, we have $vw \in \delta(U)$, contradicting the requirement that $\delta(U) \subseteq S$.

The second bullet point forces us to include $v\in U$ whenever there is a path from $s$ to $v$ that does not use any edges in $S$. To see this, apply it to the edges along this path, one at a time, to conclude that every vertex along the path must be in $U$.

This says that $U$ is forced to contain all vertices we can reach from $s$ without using any edges in $S$. Well, we can try just putting all those vertices in $U$, and no others, to see if that will work.

---

Our logic above explains why we might want to take $U$ to be the set containing $s$, and all vertices that can be reached from $s$ without taking an edge from $S$. But it doesn't prove that this will work. In fact, the arguments in the previous section don't even need to be parts of the proof; they're just "scratch work" for deciding what $U$ ought to be.

An actual proof looks something like the following:

Let $U$ be the set containing $s$, and all vertices that can be reached from $s$ without taking an edge from $S$.

Then $\delta(U)$ is an $s,t$-cut because [...]

Also, $\delta(U) \subseteq S$ because [...]

Actually, we conclude that $\delta(U)$ is an $s,t$-cut almost automatically. All we need is to know that $t \notin U$. Why is this true?

To show that $\delta(U) \subseteq S$, we should take an arbitrary edge $vw \in \delta(U)$, and show that $vw \in S$. Well, if $vw \in \delta(U)$, then $vw$ is an edge of $G$ such that $v \in U$ but $w \notin U$. Why does this imply that $vw \in S$?