Local Vertex Connectivity Between Two Vertices

Separating Two Vertices

To measure how difficult it is to disconnect two vertices by deleting other vertices, we look for the smallest set whose removal leaves them disconnected. The endpoints must remain in the graph: deleting either endpoint would not measure whether the rest of the graph keeps them connected. The definition below concerns distinct, nonadjacent vertices, so an edge directly joining the pair cannot remain after other vertices are deleted.

All graphs in this tutorial are finite and simple. A path from $u$ to $v$ is a sequence of distinct vertices beginning at $u$ and ending at $v$, with each consecutive pair adjacent. For a set $S\subseteq V(G)$, $G-S$ is the graph obtained by deleting the vertices in $S$ and all edges incident with them. The notation $u$ and $v$ are disconnected in $G-S$ means that no $u$-$v$ path remains.

Definition: Let $u$ and $v$ be distinct, nonadjacent vertices of $G$. A vertex separator for $u$ and $v$ is a set $S\subseteq V(G)\setminus\{u,v\}$ such that $u$ and $v$ are disconnected in $G-S$. The local vertex connectivity of $u$ and $v$, denoted $\kappa_G(u,v)$, is the minimum size of such a set: $$ \kappa_G(u,v)=\min\bigl\{|S|:S\subseteq V(G)\setminus\{u,v\},\ u\text{ and }v\text{ are disconnected in }G-S\bigr\}. $$

The subscript in $\kappa_G(u,v)$ records the graph in which the separation is being considered. This is a local quantity for a specified pair; it is not the global vertex connectivity $\kappa(G)$. If $u$ and $v$ are already disconnected, the empty set is a separator, so their local connectivity is $0$. If they are connected, the empty set is not a separator. Adjacent pairs are excluded from this definition: deleting vertices other than the endpoints cannot remove their edge.

Why a Minimum Always Exists

Proposition: For any distinct, nonadjacent vertices $u,v$ in a finite simple graph $G$, a separator exists and $\kappa_G(u,v)$ is defined. Moreover, $$ 0\leq \kappa_G(u,v)\leq \min\{\deg(u),\deg(v)\}. $$ If $u$ and $v$ are connected, then $\kappa_G(u,v)\geq 1$.

Proof. If $u$ and $v$ are disconnected in $G$, then $S=\varnothing$ is a separator, and the minimum is $0$. Now suppose they are connected. Since they are nonadjacent, $v\notin N(u)$. Deleting $N(u)$ therefore leaves both endpoints, and leaves $u$ with no neighbors. Because $u\neq v$, there is no $u$-$v$ path in $G-N(u)$. Thus $N(u)$ is a separator. The same argument shows that $N(v)$ is a separator. The collection of candidate sets is finite, and it contains at least these separators, so it has a minimum size. The sizes of these two particular separators are $|N(u)|=\deg(u)$ and $|N(v)|=\deg(v)$. Hence the minimum is at most both degrees. It is nonnegative because it is the size of a set. Finally, if $u$ and $v$ are connected, the empty set does not separate them, so every separator has size at least $1$. $\square$

This upper bound is useful when calculating a value: it tells us that deleting all neighbors of either endpoint will work, but it does not usually show that the resulting set is minimum. To prove a proposed value is $k$, one must do both things: exhibit a separator of size $k$, and rule out every separator of size less than $k$.

Proposition: If $S$ separates $u$ and $v$, and $S\subseteq T\subseteq V(G)\setminus\{u,v\}$, then $T$ also separates $u$ and $v$.

Proof. Suppose $S$ separates the endpoints. Every path in $G-T$ would also be a path in $G-S$, because $G-T$ is obtained by deleting at least the vertices deleted to form $G-S$. Since $G-S$ has no $u$-$v$ path, neither does $G-T$. Both endpoints remain because $T$ excludes them. Thus $T$ is a separator. $\square$

This monotonicity fact says that adding more deleted vertices cannot restore a path. It can help check that a set separates, but it does not by itself establish minimality: smaller sets must still be tested.

Calculating the Minimum

For a small explicit graph, a direct calculation can proceed by testing eligible sets in increasing order of size. First check whether the empty set separates the pair. If not, test each allowed singleton; if none separates, test pairs, and continue. Once a separator of size $k$ is found, the tests of all smaller sizes certify that $k$ is the minimum. A proposed separator can be checked by finding the connected components of the graph after deletion, or by checking directly whether a path between the endpoints remains.

Worked Example: Opposite Vertices in a 6-Cycle

Let $G$ have vertex set $V=\{1,2,3,4,5,6\}$ and edge set $E=\{12,23,34,45,56,61\}$. Find $\kappa_G(1,4)$.

The vertices $1$ and $4$ are nonadjacent: the listed edges include neither $14$ nor any other edge joining them. The graph itself has the path $1,2,3,4$, so the empty set does not separate them. The only eligible one-vertex sets are $\{2\},\{3\},\{5\},\{6\}$, since $1$ and $4$ cannot be deleted. After deleting each candidate, a path still joins the endpoints:

Deleting $2$ leaves the path $1,6,5,4$.
Deleting $3$ leaves the path $1,6,5,4$.
Deleting $5$ leaves the path $1,2,3,4$.
Deleting $6$ leaves the path $1,2,3,4$.

Thus no separator has size $0$ or $1$. Now delete $S=\{2,5\}$. The remaining vertices are $\{1,3,4,6\}$, and the only remaining edges are $34$ and $61$. Consequently $1$ and $4$ lie in separate components, so $S$ is a separator of size $2$. The complete calculation gives

\kappa_G(1,4)=2.

Check: The endpoint neighborhoods are $N(1)=\{2,6\}$ and $N(4)=\{3,5\}$. The separator $\{2,5\}$ is neither neighborhood; each neighborhood has size $2$, consistent with the upper bound, but the direct tests above establish the minimum.

Worked Example: A Pair Already Disconnected

Let $G$ have vertex set $V=\{1,2,3,4,5\}$ and edge set $E=\{12,23,45\}$. Calculate $\kappa_G(1,4)$.

The vertices $1,2,3$ form one connected component, and $4,5$ form another. In particular, there is no path from $1$ to $4$ in $G$ itself. The empty set $S=\varnothing$ is therefore a separator. No set has size less than $0$, so this separator is minimum:

\kappa_G(1,4)=0.

Check: The definition allows $S$ to be empty, and $G-S=G$; the endpoints remain disconnected. This case is why a positive local connectivity should not be assumed for every nonadjacent pair.

Worked Example: A Minimum Separator of Size Three

Let $G$ have vertex set $V=\{u,v,a,b,c\}$ and edge set $E=\{ua,ub,uc,va,vb,vc\}$, so every one of $a,b,c$ is adjacent to both $u$ and $v$, and $u,v$ are not adjacent. Find $\kappa_G(u,v)$.

The graph contains the paths $u,a,v$, $u,b,v$, and $u,c,v$, so the empty set does not separate the endpoints. An eligible separator can contain only vertices from $\{a,b,c\}$. If $S$ has size less than $3$, at most two of $a,b,c$ are deleted. At least one of them remains; call it $z$. The two edges $uz$ and $zv$ remain, so $u,z,v$ is still a path. Thus no set of size less than $3$ separates the pair.

Deleting $S=\{a,b,c\}$ leaves $u$ and $v$ with no edge between them and no other vertices. They are disconnected, so this is a separator of size $3$. Therefore

\kappa_G(u,v)=3.

Check: Both endpoint neighborhoods are $\{a,b,c\}$, whose size is $3$, matching the calculated value and the degree bound.

Worked Example: A Single Vertex Separates the Pair

Let $G$ have vertex set $V=\{u,v,a,x,y\}$ and edge set $E=\{ua,av,ux,vy\}$. Find $\kappa_G(u,v)$.

The vertices are nonadjacent, and $u,a,v$ is a path, so the empty set does not separate them. Deleting $a$ leaves the edges $ux$ and $vy$; hence $u$ and $v$ lie in different components. So $\{a\}$ is a separator of size $1$. Since size $0$ does not work, the minimum is $1$:

\kappa_G(u,v)=1.

Check: Here $N(u)=\{a,x\}$ and $N(v)=\{a,y\}$, so the one-vertex minimum separator is not equal to either endpoint neighborhood. The degree upper bound gives $\kappa_G(u,v)\leq\min\{2,2\}=2$, while the direct deletion test establishes the sharper value $1$.

Common Mistakes and a Reliable Check

Mistake: counting endpoints in the separator. In the 6-cycle example, the set $\{1,2\}$ is not an eligible separator for $1$ and $4$, even though deleting it removes a route: it deletes the endpoint $1$ itself. A separator must be a subset of $V(G)\setminus\{u,v\}$, so it measures disconnection while both specified vertices remain.

Mistake: removing a vertex from one route and stopping. In that same example, deleting $2$ removes the path $1,2,3,4$, but it does not separate the endpoints. The other path $1,6,5,4$ remains. The correction is to check whether any $u$-$v$ path remains, not merely whether one path has been destroyed.

Mistake: treating a degree bound as an exact answer. Deleting $N(u)$ always gives a separator for nonadjacent $u,v$, but it may be larger than a minimum separator. In the last example, $|N(u)|=2$, while the single vertex $a$ already separates the pair. Use endpoint neighborhoods to get an upper bound; establish equality by checking that no smaller set works.

A useful calculation record has three parts: state whether the pair is initially connected; list the smallest candidate sets and test them; then exhibit a separator of the first successful size. This makes the distinction between a working separator and a minimum separator explicit.

Check Your Understanding

For each question, keep the endpoints out of every candidate separator and verify that both endpoints remain after deletion.

Let $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. Find $\kappa_G(1,4)$.
In the graph with $V=\{u,v,a,b,c\}$ and $E=\{ua,ub,av,bv,ac\}$, find a minimum separator for $u,v$ and justify its size.
Explain why $N(u)$ is a separator for a nonadjacent vertex $v$, including why $v$ remains after deleting $N(u)$.
Give a reason why finding one separator of size $2$ does not, by itself, prove that local vertex connectivity is $2$.
For which situation does the empty set certify that the local vertex connectivity is $0$?