Comprensione della struttura della cricca

Question

Sto lavorando al seguente problema:

Ricordiamo la definizione di un grafico completo è un grafico con n vertici in modo tale che ogni vertice sia collegato a ogni altro vertice. Ricorda anche che una cricca è un sottoinsieme completo di qualche grafico. Il problema della colorazione del grafico consiste nell'assegnare un colore a ciascuno dei vertici di un grafico in modo tale che i vertici adiacenti abbiano colori diversi e il numero totale di colori utilizzati è ridotto al minimo. Definiamo il numero cromatico di un grafico G come questo numero minimo di colori richiesti per colorare il grafico G. Dimostrare che il numero cromatico di un grafico G non è inferiore alla dimensione di una clique massima di G.

Finora ho pensato al problema e ho trovato quanto segue:

• In una cricca, ogni vertice è adiacente a ogni altro vertice
• Pertanto, poiché il problema degli stati i verteci adiacenti hanno sempre colori diversi, il numero di colori necessari sarebbe il numero di verteces nella cricca
• Pertanto, il numero cromatico di qualsiasi grafico G deve essere almeno la dimensione massima della cricca, per la definizione di cricca.

Qualcuno può verificare se la mia comprensione è corretta? O sto paciosamente non capisco una cricca?