*Bounty: 50*

*Bounty: 50*

This is yet another follow-up question in the series:

Karp hardness of searching for a matching cut

Karp hardness of searching for a matching erosion

In this question, we further restrict the notion of a matching erosion (which is already a restricted notion of a matching cut). Formally, our definition is as follows.

Given an undirected graph $G(V, E)$, a **matching split** $M=(A, B)$ is a partition of $V$ into two disjoint subsets, i.e. $Acap B = emptyset land Acup B = V$ that satisfies the following conditions:

- $G[A]$ and $G[B]$ are two disjoint induced subgraphs
- The edge set of the cut $M = {uvin Evert uin A land v in B}$ is a matching (here, we abuse the notation a little bit, $M$ is both the partition $(A, B)$ and the edge set of the matching cut)
- Each vertex $uin A$ is incident to exactly one edge in $M$
- Each vertex $uin B$ is incident to exactly one edge in $M$

Clearly, we should have $|A|=|B|=|V|/2$, hence the name of this concept.

Our decision problem **Matching Split** naturally asks whether a given graph $G$ has a matching split.

Our question is: What is the complexity of deciding **Matching Split**?