Bipartitní podgraf
Úloha číslo: 3580
Ukažte, že každý graf s \(m\) hranami má bipartitní podgraf s alespoň \(\frac{m}2\) hranami.
Nápověda
Představte si, že graf tvoříte postupným přidáváním vrcholů.
Řešení
Dokážeme indukcí podle počtu vrcholů (pro jednovrcholový graf tvrzení platí).
Zvolme libovolný vrchol \(u\). Z indukčního předpokladu lze v \(G'=G\setminus u\) najít bipartitní podgraf s alespoň \(\frac{|E_{G'}|}2\) hranami. Označme \(A\) a \(B\) části (partity) tohoto bipartitního grafu.
Jednu z těchto částí rozšíříme o \(u\) a to tak, aby ve do bipartitního grafu přibylo alespoň \(\frac{\deg_G(u)}2\) hran – což jistě jde, když \(u\) přidáme do části v níž má méně sousedů.
Výsledný bipartitní podgraf má alespoň \(\frac{|E_{G'}|}2+\frac{\deg_G(u)}2=\frac{|E_{G}|}2\) hran.
