= Prime-regular subgraph from Boolean polynomial constraints
For <prime> $p$, a <graph> with $m>(p-1)n$ <edges> and maximum degree at most $2p-1$ contains a nonempty $p$-regular subgraph. Over $\mathbb F_p$, apply the <Combinatorial Nullstellensatz> on the Boolean edge-variable cube to
$$
\prod_v\left(1-\left(\sum_{e\ni v}x_e\right)^{p-1}\right)-\prod_e(1-x_e).
$$
Its full squarefree <coefficient> is nonzero because the first product has degree below $m$. A nonzero value cannot occur at the zero vector; at any other Boolean vector the second product vanishes, and the first forces all selected degrees to be multiples of $p$. The maximum-degree condition makes every positive selected degree exactly $p$.
Back to article page
