# 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)$ $\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)$ $\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.