Se \(G \) è un grafo bipartito e sia \( \Delta(G) \) il grado massimo dei sui vertici, allora \( \Delta(G) \) è uguale al numero minimo di colori necessari, denotato con \(m \) a colorare ciascun arco di \(G \) in modo tale che nessun arco adiacente abbia lo stesso colore.
Una direzione è facile infatti se \( m < \Delta(G) \) allora sia \( v \) il vertice corrispondente al grado massimo, abbiamo che da \(v \) escono esattamente \( \Delta(G) \) archi tutti adiacenti, pertanto non possiamo colorare tutti gli archi uscenti da \(v \) con colori differenti. Dunque \( m \geq \Delta(G) \) , per l'altra ho più problemi.
Supponiamo \( m > \Delta(G) \).
Sia \( G = (V,E) \) il nostro grafo e sia \( V= A \cup B \) la bipartizione di \( G \)
Siano \(M_1, M_2, \ldots, M_{\Delta(G)} \) gli insiemi corrispondenti archi colorati tutti dello stesso colore. Ovvero tutti gli archi in \(M_1 \) ad esempio sono rossi. Sappiamo che per ipotesi abbiamo che esiste \( e = (v,u) \) dove \( v \in B \) e \(u \in A \) e tale che \[ e \not\in \bigcup\limits_{i=1}^{\Delta(G)} M_i \]
\( \operatorname{deg}(u)\leq \Delta(G) \) pertanto che esiste \( M_i \), e diciamo che sia \(M_1 \) tale che nessun arco in \(M_1 \) sia connesso con \( u \).
Analogamente \( \operatorname{deg}(v)\leq \Delta(G) \) pertanto che esiste \( M_i \), e diciamo che sia \(M_2 \) tale che nessun arco in \(M_2 \) sia connesso con \( v \).
Da qui in poi non sono sicuro delle affermazioni che posso fare
Possiamo suppore che vi sia un arco in \(M_2 \) connesso con \(u \) ?
Se si allora consideriamo gli archi \( M_1 \cup M_2 \). Da cui possiamo estrarre un path \( P= (e_1,\ldots,e_j) \) di archi colorati solo con \(M_1 \) e \(M_2 \), dove \( e_{2n+1} \in M_1 \), e \( e_{2n} \in M_2 \) per ogni \( n \) tale che \( 1 \leq 2n+1, 2n \leq j \) in modo tale che le due estremità siano contenute in \( A \). Se \(u \) è un vertice di questo path \( P \), allora \( v \) non lo è perché l'unico modo in cui \( u \) e \( v \) appartengono a \( P \) è che siano le estremita poiché altrimenti sarebbero connessi con un arco di colore rispettivamente \( M_1 \) e \( M_2 \) e contraddice le ipotesi.
Se posso affermare queste cose sopra allora posso invertire i ruoli di \( M_1 \) e di \( M_2 \) all'interno del path \( P \), e creare due nuovi insiemi \(M_1' \) e \( M_2 ' \).
Ora abbiamo che sia \( u \) che \( v \) non sono connessi a nessun arco che sta in \( M_2' \) pertanto abbiamo che possiamo colorare \( e = (v,u) \) con il colore di \(M_2' \) e questo contraddice il fatto che \( m > \Delta(G) \).
Vi sembra possa funzionare?