= Solution
Choose a fixed <prime> $p\geq k$, and put $s=2p-2$. We first derive the <polynomial> step: a <graph> $H$ on $N$ <vertices> and $M>(p-1)N$ <edges>, with maximum degree at most $2p-1$, contains a nonempty $p$-regular subgraph. Use a Boolean variable $x_e$ for each <edge> and work over $\mathbb F_p$. Define
$$
R(x)=\prod_{v\in V(H)}\left[1-\left(\sum_{e\ni v}x_e\right)^{p-1}\right]-\prod_{e\in E(H)}(1-x_e).
$$
The first product has degree at most $(p-1)N<M$, while the full squarefree <monomial> $\prod_e x_e$ has <coefficient> $(-1)^{M+1}\ne0$ in the second term with its minus sign. The <Combinatorial Nullstellensatz>, with every grid $\{0,1\}$, gives a nonzero value of $R$. Since $R(0)=0$, this is a nonempty <edge> selection. The second product is then zero, so the first is nonzero. <Fermat's little theorem> makes each selected <vertex> degree zero modulo $p$. The maximum-degree bound implies that every positive selected degree is precisely $p$. This proves the <prime-regular subgraph from Boolean polynomial constraints>.
We next turn density into an almost-regular bipartite subgraph, keeping the logarithmic loss explicit. Let the original <graph> have $n\geq2$ <vertices> and $m>0$ <edges>. Some bipartition retains at least $m/2$ <edges>: choose the sides independently with <probability> $1/2$ and average the number crossing. Its average degree is at least $m/n$. Repeatedly delete a <vertex> of degree at most half the current average degree. Such a deletion cannot lower that average, since
$$
\frac{2(e-d(v))}{N-1}\geq\frac{2e}{N}\quad\Longleftrightarrow\quad d(v)\leq e/N.
$$
The process cannot delete the last positive-density <graph>, because the maintained average is positive. At termination the minimum degree is an <integer> $\sigma>m/(2n)$.
Choose the larger side $A$ of this remaining <bipartite graph>, with opposite side $B$. Keep exactly $\sigma$ <edges> at each <vertex> of $A$; choices at different <vertices> of $A$ do not conflict. Remove any now-isolated <vertices> of $B$. Thus $|A|\geq|B|$, and every <vertex> of $A$ has degree $\sigma$.
Such a half-regular <graph> contains a half-regular restriction with a <perfect matching>. Choose a minimal nonempty $X\subseteq A$ satisfying $|N(X)|\leq|X|$, which exists because the whole side $A$ satisfies this inequality. In fact equality holds: if it were strict, deleting a <vertex> of $X$ would retain the inequality, contradicting minimality; the singleton case has at least one neighbor. Every proper <subset> $Y\subset X$ satisfies $|N(Y)|\geq|Y|$. <Hall's marriage theorem> therefore supplies a <perfect matching> on $X\cup N(X)$. All $\sigma$ <edges> incident with each <vertex> of $X$ remain inside that restriction.
Delete this <perfect matching> and repeat the restriction argument. The left degrees decrease by one at each step. We obtain $\sigma$ edge-disjoint <perfect matchings> $M_0,\ldots,M_{\sigma-1}$ on nested nonempty <vertex> sets, with sizes
$$
n=N_{-1}\geq N_0\geq N_1\geq\cdots\geq N_{\sigma-1}\geq2.
$$
For any $i$ with $i+s\leq\sigma-1$, the union of $s+1=2p-1$ consecutive <matchings in a graph> has maximum degree at most $2p-1$ and at least $(s+1)N_{i+s}/2$ <edges> on $N_i$ <vertices>. If
$$
N_{i+s}>\frac{s}{s+1}N_i,
$$
it has more than $(p-1)N_i$ <edges>, so the <polynomial> step yields a $p$-regular bipartite subgraph. Every regular <bipartite graph> decomposes into <perfect matchings>: for a set in one part, counting incident <edges> gives Hall's inequality, so a <perfect matching> exists; remove it and repeat. Choosing $k$ of these $p$ <matchings in a graph> gives a nonempty $k$-regular subgraph. This is the <nested matching criterion for a regular subgraph>.
If no $k$-regular subgraph exists, every displayed size ratio must therefore satisfy the reverse inequality. Iterating at indices $0,s,2s,\ldots$ gives, with $r=\lfloor(\sigma-1)/s\rfloor$,
$$
2\leq N_{rs}\leq n\left(\frac{s}{s+1}\right)^r.
$$
Consequently $r\leq\log n/\log((s+1)/s)$ and
$$
\sigma\leq1+s\left(1+\frac{\log n}{\log((s+1)/s)}\right).
$$
Combining with $\sigma>m/(2n)$ proves the required <edge> bound. For example the finite constant
$$
c_k=2\left(\frac{1+s}{\log2}+\frac{s}{\log((s+1)/s)}\right),\qquad s=2p-2,\ p\geq k\text{ fixed prime},
$$
works for every $n\geq2$, and the case $n=1$ has no <edges>. Thus
$$
\boxed{m\leq c_k n\log n.}
$$
The logarithm comes from how often a nested <matching in a graph> <vertex> set can shrink by a fixed factor before becoming empty; it is not supplied by the <polynomial> step alone.
Back to article page
