Grafi multipartiti.

[Anér]

Premetto che non sarà un problema entusiasmante, ma gioverà senz'altro alla salute olimpica dei più giovani cercare una soluzione e pubblicarla.

Avete un naturale $k\geq 2$ e un grafo orientato, e volete dividere i vertici in $k$ sottoinsiemi $A_1,\cdots , A_k$ in modo che se una freccia parte da un vertice nell'insieme $A_i$ finisce nell'insieme $A_{i+1}$, ove gli indici sono da intendersi modulo $k$ (se volete i vari insiemi sono disposti in cerchio).
Dato $n\geq 3$, definiamo ciclo una sequenza $v_1, \cdots, v_n$ di vertici tutti distinti, a parte $v_1=v_n$, tali che per ogni $j$, considerando gli indici modulo $n$, si abbia un arco da $v_j$ a $v_{j+1}$ o un arco da $v_{j+1}$ a $v_j$ (insomma un ciclo come lo si intenderebbe nel grafo non orientato in cui si rimuovono gli orentamenti degli archi).
Dato un ciclo, definiamo come suo valore il numero $|A|-|B|$, ove $A$ è il sottoinsieme dei vertici $v_j$ tali che l'arco tra $v_j$ e $v_{j+1}$ sia orientato proprio da $v_j$ a $v_{j+1}$, e $B$ è il sottoinsieme degli altri vertici del ciclo.
Allora si può fare una partizione come richiesto sopra se e solo se ogni ciclo ha valore multiplo di $k$.

Dedurre il famoso teorema sui grafi bipartiti, sfruttando il fatto che modulo 2 la somma e la sottrazione sono la stessa operazione.