Elõször az alapdefiníciókat közöljük.

Definíció: Egy G gráf k-szorosan élösszefüggõ, ha tetszõleges k-nál kisebb elemszámú élhalmazát elhagyva a kapott gráf összefüggõ lesz.

Definíció: Egy G gráf k-szorosan (pont)összefüggõ, ha tetszõleges k-nál kisebb elemszámú csúcshalmazát elhagyva összefüggõ gráfot kapunk, és |V(G)|>k.

Megjegyzés: Az utolsó feltétellel kizártuk a kis pontszámú teljes gráfokat, amelyek ezen feltétel nélkül k-szorosan összefüggõek lettek volna.

Megjegyzés: Az egyszeres összefüggõség és egyszeres élösszefüggõség fogalma is egybeesik az összefüggõség fogalmával.

Lemma: (i) Ha egy k-szorosan élösszefüggõ gráfnak lagalább kettõ csúcsa van, akkor minden csúcsára legalább k nem hurokél illeszkedik.

(ii) Egy k-szorosan összefüggõ gráfban minden csúcsnak legalább k szomszédja van.

Bizonyítás: (i) Egy gráfban egy u csúcsra illeszkedõ összes nem hurokélet elhagyva a maradék gráfban u egy külön komponens ponthalmazát alkotja. Ha egy k-szorosan összefüggõ gráfban vagyunk és u-ra k-nál kevesebb nem hurok él illeszkedne, akkor az csak úgy lehetséges, ha V(G)={u}.

(ii) Ha egy gráfban egy u csúcsnak összes szomszédját elhagyjuk, akkor u egy egy pontú komponsnet alkot. Ha egy k-szorosan összefüggõ gráfban egy pontnak k-nál kevesebb szomszédja lenne, akkor ezek elhagyásával nem összefüggõ gráfhoz jutnánk, hiszen a maradék gráf legalább kettõ pontú (G k-szoros összefüggõségébõl adódik, hogy legalább k+1 csúcsa van). Ez ellentmond a k-szoros összefüggésnek.

Megjegyzés: Egy gráf k-szoros összefüggõségét hurokélek elhagyása, illetve két párhuzamos él esetén az egyik elhagyása nyilvánvalóan nem változtatja meg. Így összefüggõség esetén a gráfról feltehetõ, hogy egyszerû. Egy gráf k-szoros élösszefüggõségét hurokélek elhagyása nyilvánvalóan nem változtatja meg. Ugyanez nem mondható el két párhuzamos él közül az egyik elhagyásáról.

Természetesen k>l esetén egy k-szorosan összefüggõ gráf l-szeresen öszefüggõ is, és egy k-szorosan élösszefüggõ gráf l-szeresen élöszefüggõ is.

További összefüggésekre világít rá a következõ lemma.

Lemma:

(i) Ha G egy k-szorosan öszefüggõ gráf, akkor G k-szorosan élösszefüggõ is.

(ii) Ha G egy k-szorosan élösszefüggõ gráf és e egy éle, akkor G-e egy k-1-szeresen élösszefüggõ gráf.

(iii) Ha G egy k-szorosan összefüggõ gráf és v egy csúcsa, akkor G-v egy k-1-szeresen összefüggõ gráf.

(iv) Megadható olyan G k-szorosan élösszefüggõ gráf és v csúcsa, hogy G-v egy nem összefüggõ gráf.

(v) Ha G egy k-szorosan összefüggõ gráf és e egy éle, akkor G-e egy k-1-szeresen összefüggõ gráf.

Bizonyítás: (i) Legyen G egy k-szorosan összefüggõ gráf. Legyen F egy k-nál kisebb elemszámú élhalmaz (|F| < k). Célunk annak igazolása, hogy G-F összefüggõ. Ez egy egyszerû állítás, de az okoskodás az axiomatikus gondolkodáshoz való közelsége miatt sok diák számára gondot okoz. Emiatt két bizonyítást is ismertetünk.

I) G-F-et elõállítjuk G-bõl a következõ módon: egy k-nál kisebb elemszámû U csúcshalmazt elhagyunk, (U-t úgy választjuk, hogy az F-beli éleket is elhagyjuk, persze többet is elérünk ezzel: csúcsok maradnak ki és olyan élek is eltûnnek, amelyekre szükségünk van G-F-ben) majd az elhagyott pontokat egyesével visszarakjuk a ráilleszkedõ nem F-beli élekkel együtt (ezzel pontosan ``kompenzáljuk'' a korábbi csúcselhagyás túlzott hatását). G-F összefüggõsége az alábbi módon látszik: Az elsõ lépés, a k-nál kevesebb csúcs elhagyása, G k-szoros összefüggõsége miatt, összefüggõ gráfhoz vezet. Továbbá igazoljuk, hogy U összes elemének van U-n kívüli olyan szomszédja, amihez tõle nem F-beli él vezet. Ezzel elérjük, hogy a kompenzációs lépésben visszatett csúcsok kapcsolódjanak az elsõ lépés után kapott összefüggõ gráfhoz.

A továbbiakban azt részletezzük, hogy U választását, hogyan lehet a fenti feltételek mellett elvégezni. Válasszuk ki F minden elemére egyik végpontját és az így kapott csúcsokat gyûjtsük össze egy U halmazban. Belátjuk, hogy ez megfelelõ. U elemszáma nyilván nem nagyobb mint |F|, azaz kisebb mint k. U elhagyása nyilván elhagyja F összes elemét. Legyen u az U halmaz egy tetszõleges eleme. Legyen d az u csúcs azon szomszédainak száma, amelyek U-n kívül vannak és F-beli él köti össze u-val. Az U halmaz kijelölésénél az ezekhez a szomszédokhoz vezetõ d darab F-beli él mindegyikéhez az u végpontját választottuk ki. Azaz |U|<= |F|-d+1, rendezve (|U|-1)+d<= |F| Ezzel az elsõ bizonyításunkat befejeztük.

II) Tegyük fel, hogy F elhagyása után G szétesik több komponensre. Legyen A az egyik komponens ponthalmaza és B=V(G)-A, a többi csúcs által alkotott halmaz. Legyen E(A,B) azon G-beli élek halmaza, amelyek egyik végpontja A-beli, a másik B-beli. Nyilván E(A,B) az F élhalmaz részhalmaza. Legyen A_F azon A-beli csúcsok halmaza, amelyre illeszkedik E(A,B)-beli él. Hasonlóan definiálhatjuk B_F-et. Ezek után három esetet vizsgálunk

1. eset: A nem egyenlõ A_F-fel. Ekkor az A_F-beli pontok elhagyása után A-A_F elemei és B elemei közt nem vezet él, így a gráf nem összefüggõ. Mivel |A_F| <= E(A,B) <= |F| < k, ez ellentmond annak, hogy G k-szorosan összefüggõ.

2. eset: B nem egyenlõ B_F-fel. Az A és B halmazok közötti szimetria alapján a fenti gondolatmenet megismételhetõ.

3. eset: A= A_F és B=B_F. Legyen a A egy eleme. a-nak legyen d szomszédja B-ben. Mivel G k-szorosan összefüggõ, ezért a-nak legalább k szomszédja van, azaz A-beli szomszédainak száma legalább k-d. Mindegyikre legalább egy E(A,B)-beli él illeszkedik. Ez az a-ra illeszkedõ legalább d E(A,B)-beli éllel azt mutatja, hogy E(A,B)-nek legalább (k-d)+d eleme van, ami ellentmond annak, hogy az egész F halmaznak kevesebb mint k eleme van. Azaz a harmadik eset nem fordulhat elõ.

(ii) és (iii) az alapdefinícióink ismeretében triviális.

(iv) igazolásához vegyünk egy kettõ hosszú utat és helyettesítsük mindkét élét k párhuzamosan futó éllel. Az így kapott gráf, középsõ csúcsával, mint v csúccsal bizonyítja az állítást.

(v) Legyen e=xy. Legyen U egy k-1-nél keveseb elemszámú ponthalmaz G-e-ben. Be kell látnunk, hogy (G-e)-U összefüggõ.

Két esetet vizsgálunk.

1. eset: x vagy y az U halmaz eleme. Ekkor (G-e)-U=G-U és G k-szoros összefüggõségébõl adódik az állítás.

2. eset: Sem x, sem y nem U-beli. Ismét két bizonyítást ismertetünk.

I) G k-szorosan összefüggõ, így ha Ú az U halmaz bõvítve x-szel, akkor G-Ú összefüggõ. (G-e)-U megkapható ebbõl a gráfból az x csúcs és a rá illeszkedõ e-tõl különbözõ, nem U-ba vezetõ élek visszarakásával. Belátjuk, hogy x csúcs visszarakása mellett élt is rakunk vissza, ami az eredmény összefüggõségét mutatja. Ez pedig abból adódik, hogy x-nek legalább k szomszédja van, míg |U|+1 II) Ekkor (G-e)-U=(G-U)-e. G-U egy kétszeresen összefüggõ gráf. Könnyen igazolható, hogy egy H kétszeresen összefüggõ gráfból elhagyva egy élt összefüggõ gráfhoz jutunk: H-x és H-y is összefüggõ. H-e tartalmazza H-x-et és H-y-t is. H-e ponthalmaza H-x ponthalmazának és H-y ponthalmazának uniója. H-x és H-y-nak van közös csúcsa, hiszen H legalább három pontot tartalmaz. A fentiekbõl a H-x és H-y közös ponttal rendelkezõ, összefüggõ gráfok ``egymásra rakásával'' kapott gráf is összefüggõ lesz. Tehát H-e is összefüggõ.

Megjegyzés: Természetesen a lemma (ii) és (iii) állításai ismételten alkalmazható és így a következõ állításokhoz jutunk

(ii)' Ha G egy k-szorosan élösszefüggõ gráf és F egy élhalmaza, amelyre teljesül, hogy |F| < k, akkor G-F egy k-|F|-szeresen élösszefüggõ gráf.

(iii)' Ha G egy k-szorosan összefüggõ gráf és U egy csúcshalmaza, amelyre teljesül, hogy |U|

A kétszeres élösszefüggõséghez és kétszeres összefüggõséghez hasonlóan jellemezhetjük a k-szoros élösszefüggõséget és k-szoros összefüggõséget.

Tétel: A következõk ekvivalensek:

(i) G k-szorosan élösszefüggõ,

(ii) Tetszõleges x,y csúcsok esetén létezik k éldiszjunkt út, azaz k darab xy út úgy, hogy a k út élhalmazai páronként diszjunktak. (Az ilyen utakat éldiszjunkt xy utaknak nevezzük.)

Tétel: A következõk ekvivalensek:

(i) G k-szorosan összefüggõ,

(ii) Tetszõleges x,y csúcsok esetén létezik k darab pontfüggetlen út, azaz k darab xy út úgy, hogy belsõ pontjaik halmazai páronként diszjunktak (az ilyen utakat pontfüggetlen xy utaknak nevezzük), és |V(G)>k.

A tételek bizonyításához megjegyezzük, hogy a (ii)=>(i) irány egyszerû. A másik irány bizonyítása komolyabb eszközöket igényel.