A proof of Cunninghamʼs conjecture on restricted subgraphs and jump systems

For an undirected graph and a fixed integer k, a 2-matching is said to be k-restricted if it has no cycle of length k or less. The problem of finding a maximum cardinality k-restricted 2-matching is polynomially solvable when k⩽3, and NP-hard when k⩾5. On the other hand, the degree sequences of the k-restricted 2-matchings form a jump system for k⩽3, and do not always form a jump system for k⩾5, which is consistent with the polynomial solvability of the maximization problem. In 2002, Cunningham conjectured that the degree sequences of 4-restricted 2-matchings form a jump system and the maximum cardinality 4-restricted 2-matching can be found in polynomial time.In this paper, we show that the first conjecture is true, that is, the degree sequences of 4-restricted 2-matchings form a jump system. We also show that the maximum weight 4-restricted 2-matchings in a bipartite graph induce an M-concave function on the jump system if and only if the weight function is vertex-induced on every square. This result is also consistent with the polynomial solvability of the maximum weight 4-restricted 2-matching problem in bipartite graphs.