Ha vesszük egy gráfban a minimális számú lefogó éleket, és a maximális számú független éleket, akkor a gráf minden pontjához pontosan egy él fog tartozni.
Ez Gallai második tétele:
Ha egy $n$ csúcsú gráf nem tartalmaz izolált pontot, akkor
\( \rho(G) + \nu(G) = n \)
© Minden jog fenntartva!
Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!
