4 - Connectivity

Summary

A nontrivial graph is \textit {$r$-connected}, for $r\ge 0$, if it has more than $r$ vertices and no two vertices are separated by fewer than $r$ other vertices. Graphs of $d$-polytopes are $d$-connected, according to Balinski (1961). The chapter also discusses a recent result of Pilaud et al (2022) on the edge connectivity of simplicial polytopes. We examine the higher connectivity of strongly connected complexes in Section 4.3. A graph with at least $2k$ vertices is {\it $k$-linked} if, for every set of $2k$ distinct vertices organised in arbitrary $k$ pairs of vertices, there are $k$ vertex-disjoint paths joining the vertices in the pairs.Graphs of $d$-polytopes are $\floor{(d+2)/3}$-linked, but not all graphs of $d$-polytopes are $\floor{d/2}$-linked.Edge linkedness can be defined similarly by replacing vertex-disjoint paths in the definition of linkedness by edge-disjoint paths. The $d$-connectivity of a graph of a $d$-polytope is a particular case of a more general result of Athanasiadis (2009) on the connectivity of $(r,r+1)$-incidence graphs of a $d$-polytope. The chapter ends with a short discussion on the connectivity of incidence graphs.