Unique bipartite perfect matchings and cycles?

Question

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.

Answer 1

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.