A karakterizációk igazolása elõtt kimondunk ezekhez kapcsolódó két fontos tételt. Majd igazoljuk, hogy a kimondott Menger-tételbõl könyen levezethetõ a karakterizációs tétel.
Elõször egy fontos definícióra van szükségünk.
Definíció: Legyen G egy gráf, és s,t két különbözõ pontja. Egy F élhalmaz elválasztja az s és t pontokat, ha G-F-ben nincs st út, azaz az összes st út tartalmaz F-beli élt.
Tétel: (Menger-tétel, éldiszjunkt utakra vonatkozó változat) Legyen G egy (irányítatlan) gráf és s,t két pont a gráfban. Ekkor min{|F|: F élhalmaz elválasztja s-et és t-t} =max{k:létezik k éldiszjunkt st út}.
Menger tételének bizonyítása késõbb történik. Elõször a többszörös élösszefüggõség karakterizációját bizonyítjuk a Menger-tételbõl.
Következmény: 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.)
Bizonyítás: (ii)=>(i) nyilvánvaló hiszen k-nál kevesebb él elhagyása után is tetszõleges x,y csúcsok kozött lesz út (a feltételezésünk miatt G-ben létezõ k darab xy éldiszjunkt út közül legalább egy az élek elhagyása után is ``érintetlenül'' marad).
Az (i)=>(ii) irány Menger tételének ismeretében nem okoz problémát: A k-szoros élösszefüggõség miatt tetszõleges x,y pontpárra min{|F|: F élhalmaz elválasztja x-et és y-t} >= k. Menger tételének alkalmazása éppen a bizonyítandót adja.
Az élösszefüggõség esetéhez hasonlóan a többszörös összefüggõség is vizsgálható az analóg fogalmak kialakítása és megfelelõ tételek kimondása után.
Definíció: Legyen G egy gráf, és s,t a gráf két különbözõ pontja. Egy U ponthalmaz, V(G)-{s,t} egy részhalmaza, elválasztja az s és t pontokat, ha G-U-ban nincs st út, azaz az összes st út tartalmaz U-beli csúcsot.
Tétel: (Menger-tétel, pontfüggetlen utakra vonatkozó változat) Legyen G egy (irányítatlan) gráf és legyen s,t két pont a gráfban. Tegyük fel, hogy nincs st él a gráfban. Ekkor min{|U|: V(G)-{s,t}-beli U ponthalmaz elválasztja s-et és t-t}= max{k:létezik k pontfüggetlen st út}.
Elõször ismét Menger tételének egy fontos következményét írjuk le.
Következmény: (k-szorosan összefüggõ gráfok jellemzése) 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+1.
Bizonyítás: Csak az (i)=>(ii) irány okoz problémát. Legyen x,y tetszõleges pontpár G-ben. A k darab pontfüggetlen xy út létezését kell igazolnunk. Ez adódik Menger-tételbõl, ha xy nem él a gráfban. Ha xy egy e él a gráfban, akkor egy kicsit körülményesebb lesz indoklásunk. A bizoyítás befejezésére több utat is vázolunk.
I) k-ra vonatkozó teljes indukcióval igazolunk. A k=1 eset könnyen ellenõrizhetõ. Az indukcós lépéshez vizsgáljuk a G-e gráfot. Ez a gráf k-1-szeresen összefüggõ, így az indukciós állítás miatt létezik benne k-1 pontfüggetlen xy út. Az így kapott k-1 út és az xy él együtt k megfelelõ utat ad.
II)
Az xy élek száma legyen l. Ha k >= l, akkor
az xy élek felhasználásával
megadható k pontfüggetlen xy út.
Ha l