I think you can prove this using induction and the induction step will give some intuition for the situation. Let's leave out the base step (since it's trivial) and focus on the induction step, since we only care about intuition right now.
Take a graph $G = (V, E)$ and remove one arbitrary vertex $v$ and all it's adjacent edges $e_1, ..., e_k$. The resulting graph $G'$ has a cut of size $(|E| - k) / 2$ by the induction hypothesis. Now you can choose which side of the cut you put your left over vertex $v$ on. Choose the one that "adds more edges to the cut". Since you have $k$ edges adjacent to v, you add at least $k/2$ edges to the cut. So your graph $G$ has a cut of size at least $|E|/2$.
I think this step-by-step adding vertices in a way that makes the cut large gives a good intuition.
You're thinking of Kempe chains, which are a tool used in:
- some proofs of the five-color theorem for planar graphs;
- Kempe's original (wrong) proof of the four-color theorem for planar graphs;
- Maybe a few other settings as well.
Let me try to explain the idea in the context of the five-color theorem. Here, we're trying to prove that all $n$-vertex planar graphs can be vertex-colored with at most $5$ colors, by induction on $n$.
We can show that in any planar graph, there is a vertex of degree at most $5$. If we're trying to $5$-color an $n$-vertex graph $G$, we can find a vertex $v$ with $\deg(v) \le 5$, and color $G-v$ first (by the induction hypothesis). We can extend this coloring to a coloring of $G$, by giving $v$ a color not used by its neighbors, unless $v$'s neighbors use all $5$ colors between them.
If $v$ has $5$ neighbors of $5$ different colors, we need to change the coloring of $G-v$ before we can complete it to a coloring of $G$. This is what Kempe chains are good for.
Suppose that two of the colors are red and yellow. We want to recolor $G-v$ so that $v$ does not have any red neighbors. To do that,
- We take $v$'s existing red neighbor $w$, and color it yellow.
- This may cause other conflicts, if $w$ had yellow neighbors; fix them by recoloring those neighbors red.
- If $w$'s formerly-yellow neighbors had red neighbors of their own, those need to be recolored yellow, and so on.
We can keep going this way, no problem. The (red,yellow) Kempe chain containing $w$ is the set of all vertices we end up recoloring this way: swapping red to yellow and vice versa.
Once we're done, we may or may not have fixed the problem of $v$ having red neighbors. Certainly, $w$ is no longer red: it's yellow now. But what if the Kempe chain we found contains $v$'s yellow neighbor? Then that yellow neighbor becomes red; $v$ still has neighbors of all five colors.
In this case, we are saved by arguing that not all Kempe chains can loop around in this way. For example, if the colors around $v$ go red, blue, yellow, green, purple in that order, then the (red, yellow) chain and the (blue, green) chain can't both loop around, because then the chains would end up crossing.
In other applications, we make different arguments.
Best Answer
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:
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.