A gráfelméletben egy nem triviális G gráfot k - csúccsal összefüggőnek (vagy k -összefüggőnek) mondunk , ha több mint k csúcsa van, és ha k - nál kevesebb csúcsot eltávolítunk , a gráf összekapcsolt marad.
Egy gráf csúcsösszeköthetősége vagy egyszerűen konnektivitása az a legnagyobb k , amelyre a gráf k -csúcs-összekötve van.
Alternatív megoldásként egy nem teljes gráfnak van k konnektivitása , ha k a csúcsok azon legkisebb részhalmazának a mérete, amely eltávolításakor a gráf megszakad [1] . A teljes gráfokat kihagyjuk a számításból, mert nem lehet szétválasztani őket csúcsok eltávolításával. Egy n csúcsú teljes gráfnak n − 1 kapcsolata van, amint az az első definícióból következik.
Ekvivalens definíció, ha bármely gráfcsúcspárra lehetséges k , nem metsző utat találni, amelyek ezeket a csúcsokat összekötik - lásd Menger tételét ( Diestel 2005 , 55. o.). Ennek a definíciónak a válasza ugyanaz: n − 1 a K n teljes gráf összekapcsolására [1] .
Az 1-összekapcsolt gráfot összekapcsoltnak , a 2-kapcsolt gráfot duplán összekapcsoltnak , a 3-as gráfot pedig háromkapcsolatosnak nevezzük .
1- csontvázbármely k - dimenziós konvex politóp k -csúccsal összefüggő gráfot alkot (Balinski tétele , Balinski, 1961 ). A részben fordított Steinitz-tétel kimondja, hogy bármely 3 csúcshoz kapcsolódó síkgráf egy konvex poliéder vázát alkotja .