Graph explorer

Minimal Connectivity

A k-connected graph such that deleting any edge / deleting any vertex / contracting any edge results in a graph which is not k-connected is called minimally / critically / contraction-critically k-connected. These three classes play a prominent role in graph connectivity theory, and we give a brief introduction with a light emphasis on reduction- and construction theorems for classes of k-connected graphs.