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 .
Articles by others on the same topic
There are currently no matching articles.