Connectivity realization construction Created 2026-09-24 Updated 2026-11-05
Given integers , there is a finite simple graph with vertex connectivity , edge connectivity and minimum degree of a graph . Start with two disjoint cliques of size . Choose vertices in the left clique as centres of disjoint nonempty stars with a total of edges to distinct vertices of the right clique.
Deleting all cross-edges disconnects the two cliques. Every other edge cut splits at least one clique and contains at least edges, so the edge connectivity is exactly . Deleting the centres also disconnects the graph. Fewer than vertices cannot cover all cross-edges, since one edge from each star forms a matching of size ; the remaining portions of both cliques stay connected. Thus the vertex connectivity is exactly .
Some vertices in each clique have no cross-edge, so their degree is exactly ; every vertex has at least its neighbours inside its clique. The construction realizes every positive triple allowed by the Whitney inequalities for graph connectivity.
The edge connectivity is the minimum number of edges whose deletion disconnects . Deleting all edges incident with a minimum-degree vertex proves . For a minimum edge cut separating vertex sets , its endpoints on either suitable side give a vertex separator of size at most the number of cut edges; the complete-graph convention gives the same conclusion. Hence
To realize prescribed , take two disjoint copies of . Add a bipartite set of exactly cross edges whose maximum matching has size : include for , and, when , add for . This is simple because , has a matching of size , and all its edges are covered by .
Vertices untouched by cross edges have degree , so . The cross edges form an edge cut of size ; every cut that splits either clique uses at least clique edges, hence . By König's theorem, the cross graph has a vertex cover of size , whose deletion separates the two surviving clique pieces. Deleting fewer than vertices leaves each clique connected and at least one cross edge, so .