Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a bachelor thesis where one defines a superposition cycle (of a graph) is a cycle which also is a symmetric difference of two perfect matchings of that graph. I am wondering that if the symmetric difference of any two perfect matchings is always a cycle, and a superposition cycles always have even length. Someone can help me? Thanks a lot!

share|improve this question

1 Answer 1

First note that in the symmetric difference of two perfect matchings $M_1\bigtriangleup M_2$ no vertex can have degree greater than 2, so $\deg(v)\leq 2$ for any $v\in V(M_1\bigtriangleup M_2)$.

Now, also observe that no vertex can have degree 1 in $M_1\bigtriangleup M_2$ as $M_1$ and $M_2$ are perfect matchings. Therefore vertices of $M_1\bigtriangleup M_2$ have degree 0 or 2. From this it follows that $M_1\bigtriangleup M_2$ just consists of cycles and isolated vertices.

Now, any cycle in $M_1\bigtriangleup M_2$ must have even length, since $M_1$ and $M_2$ are matchings.

You can get instances where $M_1\bigtriangleup M_2$ contains more than one cycle of even length, for example consider the graph $K_{4,4}$ with bipartition $\{a,b,c,d\}$ and $\{w,x,y,z\}$. Take $M_1=\{aw,bx,cy,dz\}$ and $M_2=\{ax,bw,cz,dy\}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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