I'm looking for some help on a problem related to matchings. I've been reading literature on blossoms and flowers from Edmonds,Pulleyblank,Schrijver,Vazirani but I am having a hard time proving the following statement:
Let $G = (V,E)$ be a graph, $M$ a matching such that:
- $v\in V$ is an exposed vertex.
- There exists a vertex $x \in V$ such that there is an even alternate path $P_x$
- There exists a vertex $y \in V$ such that there is an even alternate path $P_y$. We can suppose $x\neq y$.
Let $M'$ be the matching that results from alternating the edges of the path $P_x$. In this matching $x$ is exposed and $P_x$ is an even alternate path.
I am trying to prove that there is an even alternate path between $x$ and $y$ in $M'$. My main issue with the literature I've been looking at is that in general there is only one matching and the purpose is to find a maximum matching.
My first approach was using induction over the path $P_y$, since every even subpath should also be valid for the statement. The base case is considering the subpath that has only vertex $v$, which is trivial. Lets call
The induction then would go something like: the statement holds for all subpaths $v...y_1,y_2,\dots,y_k$ with $k$ even. I want to prove that it holds for $y_{k+2}$. Then I consider the intersections between the last two edges and $P_x$ (since some edges might have flipped in $M'$). In this step there are many cases, some are easy but in some of the structure of the graph has a flower and things start getting messy. I feel there must be a theoretic result that should help me out.
I appreciate any thought, idea, or literature that could seem relevant.