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:
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:
However, Whitney’s theroem states something stronger. According to it:
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:
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 .
If for every , the edge exists. Then the number of edges in is exactly the number of all possible pairs such that . Thus:
(There are vertices in and vertices in …)
Moreover, , thus:
We can assume that (if , then and then we can think of as ).
It’s not hard to see that when the function:
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.
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:
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:
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.