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:

[S,\overline{S}]=\{\{1,6\},\{2,4\},\{3,4\}\}

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:

\kappa(G)\leq\delta(G)

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

\kappa(G)\leq\kappa^\prime(G)\leq\delta(G)

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

$\kappa^\prime(G)\leq\delta(G)$

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:

|[\{v\},V\setminus\{v\}]|=d(v)=\delta(G)

As we wanted.

$\kappa(G)\leq\kappa^\prime(G)$

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:

|\overline{S}|\cdot|S|=(V(G)-|S|)\cdot|S|

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}$ (except $u$ ).

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!

Summary

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.