Siano $v_1,\ldots,v_n$ i vertici e siano $e_1,\ldots,e_m$ gli archi. Ricordiamo che $2m$ è uguale alla somma dei gradi dei vertici del grafo, dunque:
\[m=\frac12\cdot\sum_{i=1}^n \deg(v_i)=\frac12\cdot n\cdot (2p-2)=n\cdot(p-1).\] Considero la funzione $f: \mathcal{V}\times \mathcal{E} \rightarrow \{0,1\}$ per cui $f(v_i,e_j)=1$ se l'arco $e_j$ ha come estremità il vertice $v_i$, $f(v_i,e_j)=0$ altrimenti. Adesso, prendiamo $m$ variabili $x_1,\ldots,x_m$ (ciascuna ovviamente associata ad un arco). Consideriamo il seguente polinomio in $m$ variabili:
\[P(x_1,\ldots,x_m):=\prod_{j=1}^m (1-x_j)-\prod_{i=1}^n \left[1-\left(\sum_{j=1}^m f(v_i,e_j)\cdot x_j\right)^{p-1}\right].\]
Perché sto facendo questa roba? Allora, questo è un polinomio di grado $m$ (infatti la prima produttoria ha grado $m$, mentre la seconda ha grado $n\cdot(p-1)$, che fa proprio $m$). Il coefficiente di $x_1\cdot\ldots\cdot x_m$ è $(-1)^m$, e proviene tutto dalla prima produttoria (se quello proveniente dalla seconda produttoria fosse non nullo, vorrebbe dire che ogni vertice appartiene ad ogni arco, impossibile se i vertici sono più di $2$).
E adesso.... KOMBINATORIALNULLSTELLENSATZ!
Dunque, esiste una $m$-upla $(x_1',\ldots,x_m')$ per cui $P(x_1',\ldots,x_m')\neq0$. Notiamo inoltre che $P(0,\ldots,0)=0$, quindi la $m$-upla $(x_1',\ldots,x_m')$ non è tutta nulla. Dunque il prodotto
\[\prod_{j=1}^m (1-x_j)\]
è nullo, e quindi sappiamo che
\[\prod_{i=1}^n \left[1-\left(\sum_{j=1}^m f(v_i,e_j)\cdot x_j\right)^{p-1}\right]\neq0.\hspace{1cm}(\star)\]
Modulo $p$, il valore di
\[\left(\sum_{j=1}^m f(v_i,e_j)\cdot x_j\right)^{p-1}\]
può essere $0$ oppure $1$, da $(\star)$ sappiamo dunque che fa $0$ per ogni vertice.
Consideriamo il sottografo formato da tutti gli archi $e_j$ per cui $x_j=1$. Per quanto detto sopra si deve avere che
\[\sum_{j=1}^m f(v_i,e_j)\equiv0 \pmod{p}.\]
Ma la somma a sinistra è uguale al grado di $v_i$, che quindi, essendo minore o uguale a $2p-1$, può valere o $0$ oppure $p$. Se vale $0$, elimino dal grafo il vertice $v_i$. Dopo aver eliminato tutti gli archi per cui $x_j=0$, e tutti i vertici che dopo questo trattamento hanno grado $0$, rimane un sottografo in cui tutti i vertici hanno grado $p$.