V teorii grafů říkají, že netriviální graf G je vrchol k -bvyazen (nebo k - vazba ), pokud má více než K vrcholů a po odstranění méně než K libovolných vrcholů, graf zůstává spojovacím článkem.
Vrcholová konektivita , nebo jednoduše konektivita , grafu je největší k , pro které je graf k -vertexově spojen.
Alternativně má nekompletní graf konektivitu k , pokud k je velikost nejmenší podmnožiny vrcholů, která, když je odstraněna, způsobí rozpojení grafu [1] . Úplné grafy jsou vyloučeny z úvahy, protože je nelze odstranit odstraněním vrcholů. Úplný graf s n vrcholy má souvislost n − 1, jak vyplývá z první definice.
Ekvivalentní definicí je, je-li pro libovolnou dvojici vrcholů grafu možné najít k neprotínajících se cest spojujících tyto vrcholy – viz Mengerova věta ( Diestel 2005 , s. 55). Tato definice má stejnou odpověď: n − 1 pro spojení úplného grafu K n [1] .
1-souvislý graf se také nazývá spojený , 2-souvislý graf se nazývá dvojitě spojený , 3-souvislý graf se nazývá trojsouvislý .
1- kostrajakýkoli k - rozměrný konvexní polytop tvoří k -vrcholově spojený graf ( Balinskiho teorém , Balinski, 1961 ). Částečně konverzní Steinitzova věta říká, že jakýkoli 3-vrcholově spojený rovinný graf tvoří kostru konvexního mnohostěnu .