Given a graph $G$ which is bipartite and balanced and has unique perfect matching let $G^{e}$ be $G$ without edge $e$. Let $G\cup G\_{\pi,\pi'}$ be union of $G$ and $G\_{\pi,\pi'}$ where $G\_{\pi,\pi'}$ is $G$ but having vertices of permuted by permutation $\pi,\pi'$ and an edge is in the union iff it is in either $G$ or its permutation.


**NOTATION** $\pi\in S\_n$ permutes color $1$ vertices and $\pi′\in S\_n$ color $2$ vertices. The graph $H=G\_{\pi,\pi'}$ has new edge $(i,j)$ if $(\pi^{-1}(i),\pi'^{-1}(j))$ is an edge in $G$. Remember we are specifying union and so the new permuted graph is technically considered 'different' and so we can specify union.


**Eg**: Consider graph having two vertices of color $1$ and $2$ and edge is $(1,2)$ and $(1,1)$. The permutation $\pi$ flips $1$ and $2$ of color $1$. $G\_{\pi,id}$ has edges $(2,2)$ and $(2,1)$.



> 
> **Is there a statement similar** to "If $e$ belongs to the unique perfect matching then it is true at every $\pi,\pi'$ satisfying $\pi\pi'^{-1}\neq id$ and $\pi^{-1}\pi'\neq id$ the graph $G^e\cup G^e\_{\pi,\pi'}$ has a vertex which is not part of a cycle"?
> 
> 
> 


Since union of perfect matchings in bipartite graphs is disjoint union of cycles the converse is correct. If the graph is not of unique perfect matching I think we can produce a counterexample.



Unique bipartite perfect matchings and cycles?
Counterexample: Let $G$ be a path on 10 vertices $y\_1,y\_2, \ldots y\_{10}$. This has a unique matching and this matching includes $e=y\_5y\_6$. Then $G\setminus \{e\}$ is 2 paths w $5$ vertices each; $y\_1y\_2y\_3y\_4y\_5$ and $y\_6y\_7y\_8y\_9y\_{10}$. So let $\pi\_1$ be the permutation on $\{y\_1,y\_3, y\_5,y\_7,y\_9\}$ that transposes $y\_1$ and $y\_5$ and leaves each of $y\_3$, $y\_7$, $y\_9$ fixed. Let $\pi\_2$ be the permutation on $\{y\_2,y\_4,y\_6,y\_8, y\_{10}\}$ that transposes $y\_6$ and $y\_{10}$ and leaves each of $y\_2,y\_4,y\_8$ fixed. Then every edge in $H \doteq G^e \cup G^e\_{\pi\_1,\pi\_2}$ is in a cycle. Indeed, the first component of $H$ is the path $y\_1y\_2y\_3y\_4y\_5$ plus the edges $y\_1y\_4$ and $y\_2y\_5$. The second component of $H$ is isomorphic to the first.


