# Unique bipartite perfect matchings and cycles?

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.

• It looks interesting but it is hard to follow what you mean by $G_{\pi, \pi'}$
– Mike
Feb 27, 2021 at 0:15
• $\pi$ permutes color $1$ vertices and $\pi'$ color $2$. Remember we are specifying union and so the new permuted graph is technically considered 'different' and so we can specify union. Feb 27, 2021 at 2:54
• Thanks for the edits, it does seem clearer now...
– Mike
Feb 27, 2021 at 3:33

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.