Se un grafo è bipartito, il suo numero cromatico è 2?

Si, in un grafo bipartito il numero cromatico è due.

Questo accade perché in un grafo bipartito i vertici possono essere divisi in due insiemi disgiunti, in modo tale che ogni arco del grafo colleghi un vertice di un insieme con un vertice dell'altro insieme, e non ci sono archi che collegano vertici all'interno dello stesso insieme.

Ecco un esempio di grafo bipartito.

In questo caso, il numero cromatico del grafo, che è il minimo numero di colori necessari per colorare i vertici del grafo in modo che nessun due vertici adiacenti abbiano lo stesso colore, è effettivamente 2.

Questa proprietà è una diretta conseguenza della definizione di grafo bipartito: poiché non esistono archi tra vertici dello stesso insieme, possiamo assegnare un colore a tutti i vertici di un insieme e un secondo colore diverso a tutti i vertici dell'altro insieme.

Questo assicura che due vertici connessi da un arco avranno sempre colori diversi, soddisfacendo la condizione per la colorazione dei grafi e dimostrando che il numero cromatico è 2.