Gallai második tétele | mateking
 

Gallai második tétele

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 \)