Clica maximala para si partitie cu clici egale
Posted: Sat Jul 12, 2008 7:34 pm
Fie \( G = (V, E) \) un graf cu \( \omega(G) \) par. Sa se arate ca exista \( V_{1, 2} \subseteq V \) disjuncte cu reuniunea \( V \) astfel incat \( \omega\left( G [V_1] \right) = \omega\left( G [V_2] \right) \).
[ IMO 2007/3 si Shortlist C6 ]
Nota. \( \omega(G) \) este dimensiunea maximala a unei clici (subgraf complet) din \( G \), iar \( G[S] \) reprezinta subgraful indus de \( S \subseteq V \) in \( G \).
[ IMO 2007/3 si Shortlist C6 ]
Nota. \( \omega(G) \) este dimensiunea maximala a unei clici (subgraf complet) din \( G \), iar \( G[S] \) reprezinta subgraful indus de \( S \subseteq V \) in \( G \).