For every nontrivial graph, .
These compare two numerical invariants of connectivity with the minimum degree of a graph.
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.

Articles by others on the same topic (0)

There are currently no matching articles.