Local Edge Connectivity Between Two Vertices

Separating a Specified Pair

Connectivity can be asked about a particular pair of vertices: how many edges must fail before those two vertices can no longer reach one another? This is a local question, not a question about the smallest edge cut anywhere in the graph. To answer it, we will define a separating edge cut and show how to find one by considering vertex sets that contain one endpoint but not the other.

Throughout, $G=(V,E)$ is a finite simple undirected graph, and $s,t$ are distinct vertices. For $F\subseteq E$, the graph $G-F$ is obtained by deleting the edges in $F$, while keeping all vertices. The vertices $s$ and $t$ are separated in $G-F$ if there is no path from $s$ to $t$ in $G-F$. In particular, if $s$ and $t$ are already disconnected in $G$, the empty set of edges separates them.

Definition: An $s$-$t$ edge cut is a set $F\subseteq E$ such that $s$ and $t$ are disconnected in $G-F$. The local edge connectivity of $s$ and $t$, written $\lambda_G(s,t)$, is the minimum size of such a set: $$ \lambda_G(s,t)=\min\{|F|:F\subseteq E,\ s\text{ and }t\text{ are disconnected in }G-F\}. $$

This minimum exists because there are finitely many subsets of $E$, and deleting every edge always separates distinct vertices. If $s$ and $t$ are disconnected in $G$, then $\lambda_G(s,t)=0$. If they are connected, then $\lambda_G(s,t)\ge 1$. The subscript $G$ matters: the value is attached to a specified pair in a specified graph. It is not the global edge connectivity $\lambda(G)$, which concerns cuts that disconnect the graph as a whole.

Computing with Vertex-Set Boundaries

For a vertex set $S\subseteq V$, define its edge boundary by $\partial_G(S)=\{xy\in E:x\in S,\ y\notin S\}$. Every edge in this boundary has one endpoint inside $S$ and one outside. If $s\in S$ and $t\notin S$, deleting $\partial_G(S)$ separates $s$ from $t$: after the deletion there is no edge that can take a path from inside $S$ to outside it.

Theorem: For distinct vertices $s,t$ in a finite graph $G$, $$ \lambda_G(s,t)=\min_{\substack{S\subseteq V\\s\in S,\ t\notin S}}|\partial_G(S)|. $$

Proof. For every set $S$ with $s\in S$ and $t\notin S$, deleting $\partial_G(S)$ separates $s$ from $t$, so $\partial_G(S)$ is an $s$-$t$ edge cut. Therefore $\lambda_G(s,t)\le|\partial_G(S)|$ for every such $S$.

Conversely, let $F$ be any $s$-$t$ edge cut. In $G-F$, let $S$ be the set of all vertices reachable from $s$. Then $s\in S$ and $t\notin S$. Every edge in $\partial_G(S)$ must belong to $F$: if a boundary edge were still present in $G-F$, its endpoint outside $S$ would also be reachable from $s$. Thus $\partial_G(S)\subseteq F$, and $|\partial_G(S)|\le |F|$. Taking the minimum over edge cuts gives $\min_{s\in S,\ t\notin S}|\partial_G(S)|\le\lambda_G(s,t)$. The two inequalities prove the equality. $\square$

This formula turns the problem into a search over partitions of the vertex set. It also gives a direct way to certify an answer: exhibit a boundary of the proposed size, then show every boundary separating the pair is at least that large. For small graphs, all relevant sets $S$ can be listed. For larger graphs, the formula remains useful conceptually even when listing every set is impractical.

Worked Example: Opposite Vertices of a 4-Cycle

Let $V=\{1,2,3,4\}$ and $E=\{12,23,34,41\}$. Find $\lambda_G(1,3)$. The sets $S$ containing $1$ but not $3$ are exactly $\{1\}$, $\{1,2\}$, $\{1,4\}$, and $\{1,2,4\}$.

For $S=\{1\}$, the boundary is $\{12,41\}$, of size $2$. For $S=\{1,2\}$, it is $\{23,41\}$, of size $2$. For $S=\{1,4\}$, it is $\{12,34\}$, of size $2$. For $S=\{1,2,4\}$, it is $\{23,34\}$, of size $2$. These are all possible separating boundaries, so the formula gives $\lambda_G(1,3)=2$.

Check: deleting $\{12,41\}$ isolates vertex $1$, so two edges suffice. Each of the four possible boundaries has two edges, so no set of fewer than two edges can separate the pair. Both bounds agree.

Useful Bounds and a Bridge Cut

The degrees of the endpoints give a quick upper bound. They do not, in general, determine the answer.

Proposition: For distinct vertices $s,t$, $\lambda_G(s,t)\le \min\{\deg(s),\deg(t)\}$. If $s$ and $t$ are connected, then $\lambda_G(s,t)\ge 1$.

Proof. Deleting all edges incident with $s$ leaves $s$ with no incident edges, so $s$ and $t$ are disconnected. This is a cut of size $\deg(s)$, and hence $\lambda_G(s,t)\le\deg(s)$. Deleting all edges incident with $t$ gives $\lambda_G(s,t)\le\deg(t)$. Together these imply the stated upper bound. If $s,t$ are connected, the empty deletion set does not separate them, so every separating edge set has size at least $1$. $\square$

Worked Example: Two Triangles Joined by a Bridge

Let $V=\{s,a,x,y,b,t\}$ and $E=\{sa,ax,xs,yb,bt,ty,xy\}$. Thus $s,a,x$ form one triangle, $y,b,t$ form another, and $xy$ joins the triangles. Find $\lambda_G(s,t)$.

Take $S=\{s,a,x\}$. Its boundary is exactly $\{xy\}$, so $|\partial_G(S)|=1$. The boundary formula gives $\lambda_G(s,t)\le1$. The graph is connected: within each triangle every vertex can reach every other vertex, and the edge $xy$ joins the two triangles. Therefore the lower bound in the proposition gives $\lambda_G(s,t)\ge1$. It follows that $\lambda_G(s,t)=1$.

Check: deleting the one edge $xy$ leaves $s$ in the first triangle and $t$ in the second, with no edge between the two groups. This verifies the cut directly; connectedness verifies that zero deletions cannot suffice.

When the Minimum Degree Bound Is Not Exact

The proposition’s degree bound is an upper bound, not a general formula. Even if both endpoints have degree at least two, a single edge elsewhere in the graph may be the only connection between the regions containing them. A useful calculation must account for the boundary between the regions, rather than only counting edges incident with the chosen endpoints.

Worked Example: Adjacent Vertices of a Complete Graph

Let $G=K_4$, with $V=\{1,2,3,4\}$ and $E=\{12,13,14,23,24,34\}$. Find $\lambda_G(1,2)$. The sets $S$ containing $1$ but not $2$ are $\{1\}$, $\{1,3\}$, $\{1,4\}$, and $\{1,3,4\}$.

For $S=\{1\}$, the boundary is $\{12,13,14\}$, of size $3$. For $S=\{1,3\}$, the boundary is $\{12,14,23,34\}$, of size $4$. For $S=\{1,4\}$, the boundary is $\{12,13,24,34\}$, of size $4$. For $S=\{1,3,4\}$, the boundary is $\{12,23,24\}$, of size $3$. The minimum boundary size is $3$, so $\lambda_G(1,2)=3$.

Check: deleting the three edges incident with vertex $1$, namely $\{12,13,14\}$, separates $1$ from $2$. The complete list of boundaries shows that each has at least three edges. This confirms both the upper and lower bounds.

Common Pitfall and a Reliable Check

A common mistake is to assume that the minimum degree of the endpoints equals their local edge connectivity. In the two-triangle example, $\deg(s)=2$ and $\deg(t)=2$, but $\lambda_G(s,t)=1$. The incorrect calculation “both endpoint degrees are $2$, so the local edge connectivity is $2$” mistakes an upper bound for an equality. The correction is to find an edge cut of size $1$, namely $\{xy\}$, and use connectedness to rule out a cut of size $0$.

For a small graph, a careful calculation can follow three checks:

List the vertex sets $S$ with $s\in S$ and $t\notin S$, or identify a structural reason that bounds all their boundary sizes.
Compute the edges in each relevant boundary; the boundary size is the number of edges crossing the partition, not the number of vertices on either side.
Verify both sides of the answer: a boundary of the claimed minimum size gives an upper bound, and a lower bound for every separating boundary rules out smaller cuts.

The boundary formula is particularly useful because it distinguishes a cut that is merely small from one that is minimum. Finding a small cut proves only that the local edge connectivity is no larger than its size. To establish the exact value, one must also exclude every smaller separating cut.

Check Your Understanding

Use the boundary formula and justify both the cut and the lower bound in each calculation.

Let $V=\{1,2,3,4\}$ and $E=\{12,23,34,41,13\}$. Find $\lambda_G(1,2)$ by listing the sets containing $1$ but not $2$.
Suppose $s,t$ are disconnected in $G$. What is $\lambda_G(s,t)$, and which edge set realizes the minimum?
Explain why deleting all edges incident with $s$ proves $\lambda_G(s,t)\le\deg(s)$, but does not prove equality.
In the two-triangle example, identify a vertex set whose boundary gives a cut separating $s$ from $t$.
State the boundary formula for $\lambda_G(s,t)$, including the conditions on $S$.