Proving if G is a 3-regular graph, then the size of edge cut equals size of min size of vertex cut

6.8k Views Asked by At

https://noppa.aalto.fi/noppa/kurssi/t-79.5203/luennot/slides5.pdf.pdf on page 10 of 39 is the proof. (This link may no longer be active).

It's theorem 4.1.11, which says "If G is a 3-regular graph, then $\kappa(G) = \kappa'(G)$", where $\kappa(G)$ is the minimum size of a vertex set $S$ s.t. $G-S$ is disconnected or has at least one vertex. $\kappa'(G)$ is the minimum size of edge set $F$ s.t. $G-F$ has more than one component.

What confuses me about the proof is showing why $\kappa'(G) = |S|$, where $S$ = $\kappa(G)$ is the minimum vertex cut. A procedure is provided to tell you what edges to delete. But the proof doesn't explain why the number of edges deleted equals $\kappa(G)$.

1

There are 1 best solutions below

1
On

Let S be vertex cut. G-S gives two components H1, H2. Vertices in S has one edge to vertex in H1, one edge to vertex in H2 and one edge to vertex in S. Claim is if we take edges from S to H1 they make edge cut. Since a vertex in S has only one edge to H1, we pick exactly one edge for every vertex in S (cut vertex set). Hence κ(G)=κ′(G).