I would like to show the following:
Given a graph $G=(V,E)$ with a perfect matching $P_1$ and a subgraph $G[V\setminus \{v_1,v_2,v_3,v_4\}]$ with a perfect matching $P_2$, there exists a path $w$ between two of the vertices $\{v_1,v_2,v_3,v_4\}$ with $w\subset P_1 \cup P_2$.
This question is connected to my previous question which I asked here. If this proposition is true it would help in finding an answer.
Namely, if there is such a path it would mean that I can find a matching of $G$ which matches all of $V$ except two elements of $\{v_1,v_2,v_3,v_4\}$. If I can always find matchings like this for any graph $G$ this would also answer my question.
Best Answer
In general, if we take all the vertices of a graph $G$, but only the edges in some matching of $G$, we get a spanning subgraph with maximum degree $1$ (or maybe $0$, if the matching was empty). If the matching was a perfect matching, then the subgraph is $1$-regular.
In our case, the perfect matching $P_1$ gives us a subgraph $G_1$ of $G$ in which every vertex has degree $1$. The prefect matching $P_2$ gives us a subgraph $G_2$ of $G$ in which every vertex has degree $1$ except for $v_1, v_2, v_3, v_4$, which have degree $0$.
In general, if $G_1$ and $G_2$ are the graphs with maximum degree $1$ we got from two matchings in $G$, then it makes sense to look at the symmetric difference $G_1 \mathbin{\Delta} G_2$. (This is the graph which has all the same vertices, and whose edges are the edges present in exactly one of $G_1$ or $G_2$.)
We can't say how many edges $G_1 \mathbin{\Delta} G_2$ has - that depends on how similar the two matchings are. However, every vertex that was covered by both matchings has degree either $0$ or $2$ in $G_1 \mathbin{\Delta} G_2$ (it has degree $0$ if it had the same edge in both matchings, and degree $2$ if the edged were different). Every vertex covered by only one matching has degree $1$ in $G_1 \mathbin{\Delta} G_2$. Finally, every vertex covered by neither matching still has degree $0$.
In our case, $G_1 \mathbin{\Delta} G_2$ has four vertices of degree $1$: $v_1, v_2, v_3, v_4$. Every other vertex has degree $0$ or $2$.
In general, such a symmetric difference is the union of isolated vertices, paths, and cycles. Isolated vertices are the ones which had degree $0$, so we can forget about those. Every other vertex has degree $1$ or $2$. This means that there are some components in which every vertex has degree $2$: those must be cycles. There are also components in which some vertices have degree $1$: those must be paths starting and ending at such a vertex.
In our case, $G_1 \mathbin{\Delta} G_2$ has four vertices of degree $1$: $v_1, v_2, v_3, v_4$. So it contains two paths that start and end at two of these vertices, and everything else is cycles and isolated vertices.
In particular, either one of the path components of $G_1 \mathbin{\Delta} G_2$ gives us the path you're looking for.
Your problem only asks for the path's edges to be contained in $P_1 \cup P_2$. But we can say more: the path must alternate between edges of one matching, and edges of the other. Moreover, its first and last edge must come from $P_1$, because $P_2$ does not cover the endpoints of the path. So the path we find is an augmenting path for the matching $P_2$.
With these augmenting paths, we can do the following: