1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ It looks interesting but it is hard to follow what you mean by $G_{\pi, \pi'}$ $\endgroup$ – Mike Feb 27 at 0:15
  • 1
    $\begingroup$ $\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. $\endgroup$ – 1.. Feb 27 at 2:54
  • $\begingroup$ Thanks for the edits, it does seem clearer now... $\endgroup$ – Mike Feb 27 at 3:33
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can the statement be correct after small modifications? $\endgroup$ – 1.. Feb 27 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.