Problema 2

Fie un graf neorientat cu $n$ vârfuri, pe care vrem să le împărțim în 3 mulțimi disjuncte nenule (dacă $V$ este mulțimea vârfurilor, fie $V_1, V_2, V_3$ cele trei mulțimi disjuncte, $V_1\subset V$, $V_2\subset V$, $V_3\subset V$, $V_1\cap V_2=\emptyset$, $V_1\cap V_3=\emptyset$, $V_2\cap V_3=\emptyset$). Știind că vârfurile din aceeași mulțime nu pot avea muchii între ele, care este numărul maxim de grafuri care se pot construi respectând aceste condiții pentru $n=2022$?

a) $2^{4088484}$; b) $2^{681414}$; c) $2^{2043231}$; d) $2^{1362828}$; e) $2^{4086462}$; f) $2^{2022}$.