I grafteorien siges en ikke-trivial graf G at være k - vertex - forbundet (eller k - forbundet ), hvis den har mere end k toppunkter, og efter at have fjernet mindre end k eventuelle toppunkter, forbliver grafen forbundet.
Toppunktsforbindelsen , eller blot tilslutningsmuligheder , af en graf er den største k , for hvilken grafen er k -vertex-forbundet.
Alternativt har en ikke-fuldstændig graf forbindelse k , hvis k er størrelsen af den mindste delmængde af hjørner, der, når den fjernes, gør grafen afbrudt [1] . Komplette grafer er udelukket fra overvejelse, fordi de ikke kan afbrydes ved at fjerne hjørner. En komplet graf med n toppunkter har en forbindelse på n − 1, som følger af den første definition.
En ækvivalent definition er, hvis det for et hvilket som helst par af grafhjørner er muligt at finde k ikke-skærende veje, der forbinder disse knudepunkter - se Mengers sætning ( Diestel 2005 , s. 55). Denne definition har samme svar: n − 1 for forbindelsen af hele grafen K n [1] .
En 1-forbundet graf kaldes også forbundet , en 2-forbundet graf kaldes dobbeltforbundet , en 3-forbundet graf kaldes henholdsvis triforbundet .
1- skeletenhver k - dimensionel konveks polytop danner en k -vertex-forbundet graf ( Balinskis teorem , Balinski, 1961 ). Den delvist omvendte Steinitz-sætning siger, at enhver 3-vertex-forbundet plan graf danner skelettet af et konveks polyeder .