În teoria grafurilor , un graf non-trivial G se spune că este k - conectat la vârf (sau k -conectat ) dacă are mai mult de k vârfuri și după ce se îndepărtează mai puțin de k orice vârfuri, graficul rămâne conectat.
Conectivitatea vârfurilor , sau pur și simplu conectivitatea , a unui grafic este cel mai mare k pentru care graficul este conectat la vârf k .
Alternativ, un graf necomplet are conexiune k dacă k este dimensiunea celui mai mic submulțime de vârfuri care, atunci când este îndepărtat, face graficul deconectat [1] . Graficele complete sunt excluse din considerare deoarece nu pot fi deconectate prin eliminarea vârfurilor. Un graf complet cu n vârfuri are o conexiune de n − 1, după cum rezultă din prima definiție.
O definiție echivalentă este dacă pentru orice pereche de vârfuri de graf este posibil să se găsească k căi care nu se intersectează care leagă aceste vârfuri - vezi teorema lui Menger ( Diestel 2005 , p. 55). Această definiție are același răspuns: n − 1 pentru legătura grafului complet K n [1] .
Un graf cu 1 conexiune se mai numește și conectat , un graf cu 2 conexiuni se numește dublu conectat , un graf cu 3 conexiuni se numește, respectiv, triconectat .
1- scheletorice politop convex k -dimensional formează un graf k -vertex-conectat ( teorema lui Balinski , Balinski, 1961 ). Teorema Steinitz parțial inversă afirmă că orice graf planar conectat cu 3 vârfuri formează scheletul unui poliedru convex .