Connected subgraphs, matching, and partitions

Given an undirected graph [Formula: see text] and a real edge-weight vector, the connected subgraph problem consists of finding a maximum-weight subset of edges which induces a connected subgraph of [Formula: see text]. In this paper, we establish a link between the complexity of the connected subgraph problem and the matching number. We study the separation problem associated with the so-called matching-partition inequalities, which were introduced by Didi Biha, Kerivin and Ng [Polyhedral study of the connected subgraph problem, Discr. Math. 338 (2015) 80–92] for the connected subgraph polytope.