 # A vertex of a minimum vertex cut has a neighbor in every component I'm trying to understand the sol Avah Knapp 2022-05-22 Answered
A vertex of a minimum vertex cut has a neighbor in every component
I'm trying to understand the solution for the following problem: Prove that ${\kappa }^{\prime }\left(G\right)=\kappa \left(G\right)$ when G is a simple graph with $\mathrm{\Delta }\left(G\right)\le 3$.
The solution goes like this: Let S be the minimum vertex cut, $|S|=\kappa \left(G\right)$. Since $\kappa \left(G\right)\le {\kappa }^{\prime }\left(G\right)$ always, we need only provide an edge cut of size |S|. Let ${H}_{1}$ and ${H}_{2}$ be two components of G-S. Since S is a minimum vertex cut, each $v\in S$ has a neighbor in ${H}_{1}$ and a neighbor in ${H}_{2}$. The solution conntinues from here...I really have no clue why the part "Since S is a minimum vertex cut, each $v\in S$ has a neighbor in ${H}_{1}$ and a neighbor in ${H}_{2}$." is true.
I tried to show it by contradiction but haven't gotten very far: Suppose otherwise; then there exists a vertex $v\in S$ which doesn't have a neighbor in ${H}_{1}$. We can assume that G is connected, hence there is a path joining v with $u\in V\left({H}_{1}\right)$... and I'm stuck. How do I proceed from here? Or should I try to prove this in a completely different way?
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it sag2y8s
Step 1
If a vertex $v\in S$ is not adjacent to any vertices in ${H}_{1}$, then deleting $S-\left\{v\right\}$ is already enough to separate ${H}_{1}$ from the rest of the graph.
Step 2
Therefore $S-\left\{v\right\}$ is a smaller vertex cut, which contradicts our assumption that S was a smallest vertex cut.