Reducing edge connectivity to vertex connectivity with small increase in edges
Let be a graph, we are interested in finding a graph , such that is a minor of . We want a partition of and a bijection , such that for any , and , we have .
Although there is rarely a reason to reduce edge connectivity computation to vertex connectivity computation, because vertex connectivity is much harder in almost every way. It is still a interesting exercise.
The naive method: For each vertex , expand it into a clique of size , and find a bijective label between new vertex in the clique with the edges incident to . Connect all the vertices with the same label. Thus in the worst case, we can loosely bound the edges in to be .
There is another way with the edge blow up to be .
However, we want to blow up the number of edges by at most .
A -connector is a graph with two disjoint set of vertices (inputs) and (outputs) such that , and for any bijection , there exist vertex disjoint paths connecting and simultaneously.
It is known a -connector exists with edges, because there is a even stronger notion of -nonblocking graph.
-connector seems to be what we need here, but it forces us to have input and output vertices. Thus we can define the following.
A -symmetric-connector is a graph with a set of vertices , such that for any a bijection between two disjoint subsets of , there exist vertex disjoint paths connecting and simultaneously.
Let be a -connected with inputs and outputs , we construct a -symmetric connector by make a copy of as , maintaining the edges of the copies too. Then we pick any bijection between and , and contract and into one vertex. The contracted vertex will be the set , and the new graph is a -symmetric-connector.
 Z. Galil, G.F. Italiano, Reducing edge connectivity to vertex connectivity, SIGACT News. 22 (1991) 57–61 10.1145/122413.122416.
 F.R.K. Chung, On concentrators, superconcentrators, generalizers, and nonblocking networks, Bell System Technical Journal. 58 (1979) 1765–1777 10.1002/j.1538-7305.1979.tb02972.x.