Clica maximala para si partitie cu clici egale

[Filip Chindea]

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