Edge Connectivity

In the last post I’ve presented the term of Connectivity, vertex-cut and cut-vertices. I also mentioned that we can disconnect a graph with edges. So that what I am going to talk about here – The term of Edge Connectivity.

Some new definitions

Suppose that G=(V,E) is a graph.

  • A set F\subseteq E of edges is said to be a separator if G\setminus F = (V,E\setminus F) is not conneceted.
  • The graph is called k-edge-connected if every separator F is at least of size k. i.e. |F|\geq k.
  • The edge-connectivity is the greatest k such that G is k-edges-connected. We denote it as \kappa^{\prime}(G).

So far, this is pretty similar to the definitions realted to vertices. However, there is another definition I would like to present:

Suppose that S is a non-empty set of vertices (but not all of them). We define the cut[S,\overline{S}] as the collection of edges with one endpoint in S, and one in \overline{S} (which is the complement).

Let’s see an example, consider the following graph:

Suppose that S=\{1,2,3\}. Let’s mark the vertices of S in the graph in blue. The rest I’ll mark in red:

Now, let’s mark the edges that has one blue endpoint and one red endpoint:

The marked edges are the elements of [S,\overline{S}]. To summarize:


Notes on the definitions

Just like the we said in the last post, If the graph is not connected – then the empty set is a valid separator. In that case, we say that the graph is 0-edge-connected and has edge-connectivity 0.

In adittion, note that every separator contains a cut. Why?

Let F be a non-empty separator and observe G\setminus F It is not connected. Then (in G\setminus F) we can choose one component A and define S to be the set of the vertices of A.

There are no edges between S and \overline{S} in G\setminus F). Thus, if in the original graph there is an edge between S and \overline{S} – it must be in F. Therefore, [S,\overline{S}]\subseteq F.

From that distinction we can easily conclude that a minimal separator is a cut:

If F is a minimal separator, it contains a cut [S,\overline{S}]. However, [S,\overline{S}] is also a separator (Why?). By the minimality of F we get that F=[S,\overline{S}].

Connection with connectivity

There is a famous theorem due to Whitney that shows us a clear connection between \kappa(G),\kappa^{\prime}(G) and \delta(G). We’ve already seen that:


However, Whitney’s theroem states something stronger. According to it:


That’s pretty nice, it gives us another bound to \kappa(G), a better bound! Let’s prove this theorem:


Our goal is to find a separator with size that is smaller than or equals \delta(G). That’s not a problem though.

Suppose that v\in G is a vertex with minimal degree. The cut [\{v\},V\setminus\{v\}] is a separator. The number of edges in it are the number of edges that are adajcent to v – which is the degree of v. Since v has minimal degree, we get that d(v)=\delta(G). Therefore:


As we wanted.


Our goal is to show that every separator has a bigger size then \kappa(G). That is, the minimal number of edges required to disconnect the graph is bigger than the greatest number of vertices required to dosconnect the graph.

So let’s pick a minimal separator. We’ve seen that a minimal separator is a cut, thus we can denote it by [S,\overline{S}]. And we know that \kappa^\prime (G) = |[S,\overline{S}]|.

Case 1

If for every u\in S, v\in \overline{S}, the edge \{u,v\} exists. Then the number of edges in [S,\overline{S}] is exactly the number of all possible pairs (u,v) such that u\in\overline{S},v\in S. Thus:

\kappa^\prime(G)=|[S,\overline{S}]|=|\{(u,v):u\in\overline{S},v\in S\}|=|\overline{S}|\cdot|S|

(There are |\overline{S}| vertices in \overline{S} and |S| vertices in S…)

Moreover, |\overline{S}|=V(G)-|S|, thus:


We can assume that 1\leq |S| \leq \frac{V(G)}{2} (if |S| > \frac{V(G)}{2}, then |\overline{S}| < \frac{V(G)}{2} and then we can think of \overline{S} as S).

It’s not hard to see that when 1\leq |S|\leq \frac{V(G)}{2} the function:

f(|S|)=(V(G)-|S|)\cdot |S|

Gets it’s local minimal value when |S| = 1. Therefore:

(V(G)-|S|)\cdot|S|\geq (V(G)-1)\cdot 1=V(G) -1

Recall that V(G) - 1 is an upper bound to \kappa(G). Therefore, in total we now have:

\kappa^\prime(G)\geq V(G) -1\geq \kappa(G)

As we wanted.

Case 2

There are v\in\overline{S}, u\in S such that \{u,v\} is not an edge in G.

Denote by A the set of vertices that are adjacent to u is \overline{S}.

In addition, denote by B the set of vertices in S that have neighbors in \overline{S} (exceptu).

Now I’m interested in the set A\cup B. By removing the vertices of A\cup B from the graph, we remove all the possible paths between u,v. Thus, A\cup B is a vertex cut. Therefore:

|A\cup B|\geq\kappa(G)

On the other hand, every edge from u to A is in the cut [S,\overline{S}]. In addition, all the edges from a vertex of B to \overline{S} are in the cut as well.

So the cut contains at least |A\cup B| edges (one edge for each v\in A\cup B). Thus:

\kappa^\prime(G)=|[S,\overline{S}]|\geq|A\cup B|

We now combine those results to get:

\kappa^\prime(G)\geq |A\cup B|\geq \kappa(G)

As we wanted!


So that was a shorter post than the previous one. Although, we have met a respectful amount of definitions, and proved a really nice theorem.

In the next post, I am going to keep discussing about connectivity. I am going to present a main theorem in the topic – Menger’s theorem.

Leave a Reply

%d bloggers like this: