k-szorosan élösszefüggő gráf
olyan gráf, mely bármely k‒1 él elhagyásával is összefüggő marad / From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén G összefüggő gráfot akkor nevezünk k-szorosan élösszefüggő vagy k-élösszefüggő gráfnak, ha kevesebb mint k él eltávolítása után minden esetben összefüggő marad.
Egy gráf élösszefüggősége (jelölése: κ’(G) vagy λ(G)) az a legnagyobb k szám, amire igaz, hogy a gráf k-szorosan élösszefüggő.
Adott gráfban a csúcsösszefüggőség, az élösszefüggőség és a minimális fokszám között fennáll, hogy κ(G) ≤ κ’(G) ≤ δ(G).
Az élösszefüggőséget és a k-szorosan élösszefüggő gráfok leszámlálásának problémáját Camille Jordan már 1869-ben tanulmányozta.[1]