Take the tour ×

I am reading A simple min-cut algorithm (Stoer & Wagner, 1997), and the proof uses some terms I don't understand.

Specifically I am unclear on what is meant by "$C_v$ the cut of $A_v \cup \{v\}$ induced by $C$". In the context, $C$ is an $s$-$t$-cut of a graph $G$, and $A_v \cup \{v\}$ is a subset of vertices of $G$.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

This is a part of the proof of

LEMMA 3.1. Each cut-of-the-phase is a minimum s-t-cut in the current graph, where $s$ and $t$ are the two vertices added last in the phase.

$A_{v}$ the set of all vertices added before $v$, so $A_{v} \cup {v}$ the set of all vertices added before $v$ including $v$.

$C_{v}$ is just the cut of $A_{v} \cup {v}$ on all vertices of $G$. Obviously all $C_{v}$'s are different because they are cuts for different sets of vertices, but all these vertices are vertices of initial graph $G$ (with the same edges as edges of graph $G$, but of course $C_{v}$ has less edges that $G$, all vertices of $C_{v}$ are the vertices of $G$, but $G$ may have more vertices). So think of $C_{v}$ as a subgraph of $G$, there is no something new in $C_{v}$ that $G$ doesn't have.

The more official definition from Glossary of graph theory:

A subgraph $H$ of a graph $G$ is said to be induced if, for any pair of vertices $x$ and $y$ of $H$, $xy$ is an edge of $H$ if and only if $xy$ is an edge of $G$. In other words, $H$ is an induced subgraph of $G$ if it has exactly the edges that appear in $G$ over the same vertex set. If the vertex set of $H$ is the subset $S$ of $V(G)$, then $H$ can be written as $G[S]$ and is said to be induced by $S$.


Let's be more specific about the algorithm. I think wlog we can consider $C_{v}$ as $C$, it doesn't contradict the definition of induced graph and works great to show what the algorithm does. According to the algorithm we approach the last vertex by taking the largest in terms of weight edges. Therefore as the cut we have the lightest edges so obviously it's the minimum s-t in comparison to any arbitrarily taken s-t cut.

Please take a look at the following description Simple min cut algorithm. It provides with very good example.

share|improve this answer
Thanks for your reply. I still don't understand what a "cut of a set of vertices X" is, or why you refer to $C$ as a graph. In my understanding, $C=(S,T)$ is a partition of the vertices of $G$. Is the cut $C_v = (S \cap X, T \cap X)$ ? Perhaps if you could give an example it would be helpful :) –  mitchus Mar 2 '12 at 12:05
@mitchus: OK, I understood you, ignore the the first part of answer, I added some to answer, in short, you are right, G is a graph. The best example I've found is attached. –  com Mar 2 '12 at 14:27
If I understand correctly, according to your link (slide 49), the induced cut $C_v$ is the cut $C$ limited to the subgraph $G'$ of $G$ induced by the nodes $A_v \cup \{v\}$. Would you agree with that? –  mitchus Mar 5 '12 at 7:28
yes, sounds reasonable –  com Mar 6 '12 at 7:57
add comment

Your Answer


