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 \)
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.
1.
Adjuk meg az alábbi gráf maximális független élhalmazának és minimális lefogó élhalmazának számát.
