A Result on Cut Vertices

52 Views Asked by At

This is one of the steps used to prove Menger's theorem in question 4 part (iii) of https://uwaterloo.ca/combinatorics-and-optimization/sites/ca.combinatorics-and-optimization/files/uploads/files/graph-theory-2001.pdf

Suppose $W$ is a vertex cut of $G$ separating $a$ and $b$ of size $k$, such that neither $a$ nor $b$ is adjacent to all vertices of $W$. Define $G_a$ to be the graph obtained by replacing the component of $G - W$ containing $a$ by a single vertex $a_0$, and joining $a_0$ to all of $W$. Prove that there are $k$ disjoint paths from $a_0$ to $b$ in $G_a$

(top image is original graph, bottom image is $G_a$). It's clear to see that $|W| = 3$ and yet there are only 2 vertex disjoint paths from $a_0$ to $b$ in $G_a$.

1

There are 1 best solutions below

2
On BEST ANSWER

Two things are going on.

First of all, in the proof, $k$ is the minimum size of a vertex cut of $G$ that separates $a$ and $b$, and $W$ is a vertex cut of that size. Therefore the counterexample is not valid: in the graph shown, there is an $a-b$ vertex cut of size $1$, but $|W|=3$.

Second of all, by Menger's theorem, the claim is true whether or not $a$ or $b$ are adjacent to all of $W$. (*) We can check that in $G_a$, $k$ remains the minimum size of a vertex cut of $G$ that separates $a_0$ and $b$, and then the existence of $k$ disjoint paths connecting $a_0$ to $b$ is precisely what Menger's theorem promises us.

Of course, we can't use Menger's theorem here, because we are in the process of proving that theorem! That is precisely why we are assuming that neither $a$ nor $b$ is adjacent to all of $W$. When this holds, the component of $G-W$ containing $a$ contains more than one vertex, and therefore $G_a$ has fewer vertices than $G$.

Why is this relevant? Because in the proof, $G$ is chosen to be the smallest counterexample to Menger's theorem. (We are assuming for the sake of contradiction that such a counterexample exists.) Since $G_a$ is smaller than $G$, then $G_a$ is not a counterexample, and therefore Menger's theorem must hold in $G_a$. This turns things around: now, even though we are in the middle of proving Menger's theorem, we can apply Menger's theorem to $G_a$, and so the earlier argument (*) works.