= Nested matching criterion for a regular subgraph
Let $p$ be <prime> and set $s=2p-2$. If a <bipartite graph> has edge-disjoint <perfect matchings> $M_0,\ldots,M_{\sigma-1}$ on nested nonempty <vertex> sets, and $|V(M_{i+s})|>s|V(M_i)|/(s+1)$, then the union of $s+1$ consecutive <matchings in a graph> has maximum degree at most $2p-1$ and more than $(p-1)|V(M_i)|$ <edges>. The <prime-regular subgraph from Boolean polynomial constraints> gives a $p$-regular subgraph. Its <perfect matching> decomposition gives a $k$-regular subgraph for every $k\leq p$. If none exists, every $s$ steps shrink the <vertex> set by factor at most $s/(s+1)$, bounding $\sigma$ by a constant times $\log n$.
Back to article page
