Se dă un graf cu $N + 1$ numerotate de la $0$ la $N$. Există muchii de la nodul $N$ la toate celelalte $N$ noduri şi între oricare două noduri $A$ şi $B$ cu proprietatea că $A, B < N$ şi $(A + 1) = B$ mod $N$. Se observă că numărul total de muchii este $2 * N$.

h2. Cerintă

h2. Cerinţă

Se cere să coloraţi muchiile grafului cu un număr cît mai mic de culori astfel încat între oricare două noduri să existe cel puţin un drum care conţine doar muchii colorate distinct.