Nested matching criterion for a regular subgraph
ID: nested-matching-criterion-for-a-regular-subgraph
Let be prime and set . If a bipartite graph has edge-disjoint perfect matchings on nested nonempty vertex sets, and , then the union of consecutive matchings in a graph has maximum degree at most and more than edges. The prime-regular subgraph from Boolean polynomial constraints gives a -regular subgraph. Its perfect matching decomposition gives a -regular subgraph for every . If none exists, every steps shrink the vertex set by factor at most , bounding by a constant times .
New to topics? Read the docs here!