Why is this simple proof of the fact $\kappa(G)\le \lambda(G)$ is wrong?

129 Views Asked by At

A standard result in graph theory(more specifically graph connectivity) is that $\kappa(G)\le \lambda(G)$, where $\kappa(G)$ is the size of vertex cut set of $G$ and $\lambda(G)$ is the size of the edge cut set of $G$.
The proof(s) I have seen so far are not trivial. But why can't I argue as follows:
Let $\{x_1y_1,\cdots,x_ky_k\}$ be a bridge set of $G$. Then the vertex set $\{x_1,x_2,\cdots,x_k\}$ is a cut set of $G$, because deleting the vertex $x_i$ also deletes the edge $x_iy_i$.

Where am I going wrong?

1

There are 1 best solutions below

1
On

The way I like to present the proof in a graph theory class starts from your idea and iterates.

We'd like to just take an edge cut $X$ and, for each edge $e \in X$, delete one endpoint of $e$. The trouble is that this might eat an entire component of $G-X$, leaving a connected graph behind.

To fix this, we can pick vertices $v,w$ in two different components of $G-X$ and "protect" them: whenever we delete an endpoint of $e \in X$, make sure it's not $v$ or $w$. The trouble now is that $vw$ might be an edge in $X$, in which case $v$ and $w$ can't both be protected.

To fix this, we can pick non-adjacent vertices $v,w$. This works unless $X$ contains all $k(n-k)$ edges between the two components of $G-X$, so non-adjacent $v,w$ cannot be found.

We don't fix this last problem; here, we just observe that $k(n-k) \ge n-1 \ge \delta(G) \ge \kappa(G)$, so in this case we already have the inequality we want.