I grafteorin sägs en icke-trivial graf G vara k - vertex -ansluten (eller k -ansluten ) om den har fler än k hörn och efter att ha tagit bort mindre än k några hörn, förblir grafen ansluten.
Vertex connectivity , eller helt enkelt connectivity , för en graf är den största k för vilken grafen är k -vertex-ansluten.
Alternativt har en ofullständig graf anslutning k om k är storleken på den minsta delmängden av hörn som, när den tas bort, gör grafen frånkopplad [1] . Kompletta grafer utesluts från beaktande eftersom de inte kan kopplas bort genom att ta bort hörn. En komplett graf med n hörn har sambandet n − 1, enligt den första definitionen.
En ekvivalent definition är om det för något par av grafhörn är möjligt att hitta k icke-korsande vägar som förbinder dessa hörn – se Mengers sats ( Diestel 2005 , s. 55). Denna definition har samma svar: n − 1 för kopplingen av hela grafen K n [1] .
En 1-kopplad graf kallas också kopplad , en 2-kopplad graf kallas dubbelkopplad , en 3-kopplad graf kallas respektive trikopplad .
1- skelettvilken k - dimensionell konvex polytop som helst bildar en k -vertex-kopplad graf ( Balinskis teorem , Balinski, 1961 ). Den delvis omvända Steinitz-satsen säger att varje 3-vertex-ansluten plan graf bildar skelettet av en konvex polyeder .