= Connectivity realization construction
Given integers $1\leq k\leq\ell\leq d$, there is a finite <simple graph> with <vertex connectivity> $k$, <edge connectivity> $\ell$ and <minimum degree of a graph> $d$. Start with two disjoint <cliques> of size $d+1$. Choose $k$ vertices in the left clique as centres of disjoint nonempty stars with a total of $\ell$ edges to distinct vertices of the right clique.
Deleting all $\ell$ cross-edges disconnects the two cliques. Every other edge cut splits at least one clique and contains at least $d$ edges, so the <edge connectivity> is exactly $\ell$. Deleting the $k$ centres also disconnects the graph. Fewer than $k$ vertices cannot cover all cross-edges, since one edge from each star forms a <matching> of size $k$; the remaining portions of both cliques stay connected. Thus the <vertex connectivity> is exactly $k$.
Some vertices in each clique have no cross-edge, so their degree is exactly $d$; every vertex has at least its $d$ neighbours inside its clique. The construction realizes every positive triple allowed by the <Whitney inequalities for graph connectivity>.
Back to article page