What is the definition of an induced cut

Question

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$.

Answer 1

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$.

Addendum:

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.