To determine if such a matching exists is NP-complete. We reduce 3SAT to this problem of determining if there is a matching with adjacent vertices.
We create 3 gadgets:
- separator gadget
- variable gadget
- clause gadget
Separator gadget
The separator gadget is used to ensure that there is no influence between different gadgets. It consists of one vertex in the left partite set connected to one vertex in the right partite set. Greedily, we can assume would always be always taken because it preserves valid matchings. For the following gadgets, whenever we obtain adjacent vertices from the left partite set, we assume that these are separated from other gadgets by this separator gadget.
Variable gadget
The simplest variable gadget consists of 3 adjacent vertices $v_k,v_{k+1},v_{k+2}$ in the left partite set. $v_k,v_{k+1},v_{k+2}$ are respectively connected to (distinct) $w_{v_k},w_{v_{k+1}},w_{v_{k+2}}$ in the right partite set. The effect is we have to match $(v_{k+1},w_{v_{k+1}})$ or we have to match $(v_k,w_{v_k}),(v_{k+2},w_{v_{k+2}})$.
The idea: We can form subsets $w_{x_i}$ and $w_{\lnot x_i}$ of the right partite set, where we guarantee that $w_{x_i}$ or $w_{\lnot x_i}$ is "consumed".
So far, we have demonstrated a variable gadget where $w_{x_i}=\{w_{v_k},w_{v_{k+2}}\}$ and $w_{\lnot x_i}=\{w_{v_{k+1}}\}$. We want to show that we can build arbitrarily large variable gadgets $(w_{x_i},w_{\lnot x_i})$, i.e. for any positive integer $N$, we can have $|w_{x_i}|,|w_{\lnot x_i}|>N$.
Take a variable gadget $(w_{x_i},w_{\lnot x_i})$. It suffices to construct a variable gadget $(w'_{x_i},w'_{\lnot x_i})$ with $|w'_{x_i}|=|w_{x_i}|+1,|w'_{\lnot x_i}|=|w_{\lnot x_i}|$. (The roles of $w_{x_i},w_{\lnot x_i}$ can be swapped.)
Take $w\in w_{x_i}$, and obtain three adjacent vertices in the left partite set $v'_k,v'_{k+1},v'_{k+2}$. Connect $(v'_{k+1},w)$, and obtain two more vertices in the right partite set $w_{v'_k},w_{v'_{k+2}}$, connecting $(v'_k,w_{v'_k}),(v'_{k+2},w_{v'_{k+2}})$. When we start by matching the vertices in $w_{x_i}$, we cannot match $v'_{k+1}$, and hence we have to also match $w_{v'_k}$ and $w_{v'_{k+2}}$. Our new variable gadget is $(w'_{x_i},w'_{\lnot x_i})=((w_{x_i}\setminus\{w\})\cup\{w_{v'_k},w_{v'_{k+2}}\},w_{\lnot x_i})$.
Clause gadget
For each clause $C_i=y_{i,1}\lor y_{i,2}\lor y_{i,3}$ (where $y_{i,j}$ is some variable $x_*$ or negation $\lnot x_*$), we obtain two adjacent vertices in the left partite set $v_k,v_{k+1}$ and pick fresh elements (not used in other clause gadgets) $w_{i,1}\in w_{y_{i,1}},w_{i,2}\in w_{y_{i,2}},w_{i,3}\in w_{y_{i,3}}$. Connect all of $\{v_k,v_{k+1}\}$ to all of $\{w_{i,1},w_{i,2},w_{i,3}\}$.
Proof it works
Suppose 3SAT instance is satisfiable. For each variable or negation $y\in\{x,\lnot x\}$ which is chosen to be true, only use $w_{\lnot y}$ to match the vertices in the left partite set for the variable gadget. For each satisfied clause, pick a variable which is true, and do a corresponding matching.
Suppose we have such a matching. Then from the variable gadgets, we get an assignment based on $w_{x_i}$ or $w_{\lnot x_i}$ is fully used to match the vertices in the left partite set for the variable gadget. The construction ensures this. If both are fully used, choose arbitrarily - this variable is not used to satisfy any clause. Hence the 3SAT instance is satisfiable.
