Graafiteoriassa ei-triviaalin graafin G sanotaan olevan k - vertex -yhdistetty (tai k -kytketty ), jos sillä on enemmän kuin k pistettä ja kun on poistettu vähemmän kuin k pistettä, graafi pysyy kytkettynä.
Graafin kärkiliitettävyys , tai yksinkertaisesti liitettävyys , on suurin k , jolle graafi on k -vertex-kytketty.
Vaihtoehtoisesti epätäydellisellä graafilla on liitettävyys k , jos k on pienimmän pisteiden osajoukon koko, joka poistaessaan graafin katkeaa [1] . Täydelliset graafit jätetään huomioimatta, koska niitä ei voida irrottaa pisteitä poistamalla. Täydellisellä graafilla, jossa on n pistettä, on yhteys n − 1, kuten ensimmäisestä määritelmästä seuraa.
Vastaava määritelmä on, jos mille tahansa graafin kärkiparille on mahdollista löytää k ei-leikkautuvaa polkua, jotka yhdistävät nämä kärjet - katso Mengerin lause ( Diestel 2005 , s. 55). Tällä määritelmällä on sama vastaus: n − 1 täydellisen graafin K n yhteydelle [1] .
1-liitettyä graafia kutsutaan myös yhdistetyksi , 2-kytkettyä graafia kutsutaan kaksinkertaiseksi , 3-liitettyä graafia kutsutaan vastaavasti kolmikytketyksi .
1 - luurankomikä tahansa k - ulotteinen konveksi polytooppi muodostaa k -vertex-kytketyn graafin ( Balinskin lause , Balinski, 1961 ). Osittain käänteinen Steinitzin lause sanoo, että mikä tahansa 3-pisteisiin kytketty tasograafi muodostaa kuperan monitahoisen rungon .