Niech \(\displaystyle{ G}\) będzie grafem takim, że dowolne dwa cykle długości nieparzystej się przecinają (czyli mają wspólny wierzchołek). Udowodnij, że \(\displaystyle{ \chi(G) \le 5}\) .
Próbowałem to udowodnić korzystając z algorytmu zachłannego, ale nic nie wychodzi. Później próbowałem nie wprost, czyli trzeba użyć przynajmniej \(\displaystyle{ 6}\) kolorów, aby pokolorować \(\displaystyle{ G}\) , więc istnieją zbiory \(\displaystyle{ A_1,..,A_6}\) rozłączne niepuste i takie, że \(\displaystyle{ \forall_{i=1,...,6} \forall_{x,y \in A_i} xy \notin E(G)}\) oraz \(\displaystyle{ \forall_{i,j=1,...,6 i \neq j } \exists_{x \in A_i} \exists_{y \in A_j} xy \in E(G)}\) i chciałem pokazać, że znajdę dwa rozłączne cykle długości \(\displaystyle{ 3}\) , ale też mi się nie udało.
Jak to zrobić?