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 is a graph.

- A set of edges is said to be a
**separator**if is not conneceted. - The graph is called
**-edge-connected**if every separator is at least of size . i.e. . - The
**edge-connectivity**is the greatest such that is -edges-connected. We denote it as .

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

Suppose that is a **non-empty** set of vertices (but **not** all of them). We define the **cut** – as the collection of **edges** with one endpoint in , and one in (which is the complement).

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

Suppose that . Let’s mark the vertices of 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 . 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 be a non-empty separator and observe It is not connected. Then (in ) we can choose one component and define to be the set of the vertices of .

There are no edges between and in ). Thus, if in the original graph there is an edge between and – it must be in . Therefore, .

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

If is a minimal separator, it contains a cut . However, is also a separator (Why?). By the minimality of we get that .

## Connection with connectivity

There is a famous theorem due to Whitney that shows us a clear connection between and . 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 , a **better** bound! Let’s prove this theorem:

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

Suppose that is a vertex with minimal degree. The cut is a separator. The number of edges in it are the number of edges that are adajcent to – which is the degree of . Since has minimal degree, we get that . Therefore:

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

As we wanted.

Our goal is to show that every separator has a bigger size then . 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 . And we know that .

**Case 1**

If for every , the edge exists. Then the number of edges in is exactly the number of all possible pairs such that . Thus:

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

(There are vertices in and vertices in …)

Moreover, , thus:

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

We can assume that (if , then and then we can think of as ).

It’s not hard to see that when the function:

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

Gets it’s local minimal value when . Therefore:

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

Recall that is an upper bound to . Therefore, in total we now have:

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

As we wanted.

**Case 2**

There are such that is not an edge in .

Denote by the set of vertices that are adjacent to is .

In addition, denote by the set of vertices in that have neighbors in (except).

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

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

On the other hand, every edge from to is in the cut . In addition, all the edges from a vertex of to are in the cut as well.

So the cut contains at least edges (one edge for each ). 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**.