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.