A vertex of a minimum vertex cut has a neighbor in every component

discrete mathematicsgraph theory

I'm trying to understand the solution for the following problem: Prove that $\kappa'(G)=\kappa(G)$ when $G$ is a simple graph with $\Delta(G) \leq 3$.
The solution goes like this: Let $S$ be the minimum vertex cut, $|S|=\kappa(G)$. Since $\kappa(G)\leq \kappa'(G)$ 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(H_1)$and I'm stuck. How do I proceed from here? Or should I try to prove this in a completely different way?

Best Answer

If a vertex $v \in S$ is not adjacent to any vertices in $H_1$, then deleting $S - \{v\}$ is already enough to separate $H_1$ from the rest of the graph. Therefore $S - \{v\}$ is a smaller vertex cut, which contradicts our assumption that $S$ was a smallest vertex cut.