Distribute to pairs with efficient algorithms

Question

The task is to find a efficient algorithm to the following problem. There are n boys and n girls who need to be divided to pairs. You get a list with all possible pairs that could be made. It means that if the pair (a,b) is in the list then the boy a can be paired with the girls b.

It is known that each boy appears in exactly two pairs, and each girls appears exactly in two pairs. I need to find an algorithm which will find me a proper division to pairs.

My idea was to define a graph. The vertices will be the n boys and the n girls. The edge (a,b) Will be in the graph if the pair (a,b) is the list of possible pairings.

Because each boy and girl appear in exactly two pairs, then each vertex in the graph will be of degree 2. So every vertex in the graph will be of an even degree.

A connected graph with vertices that are only of even degree has an euler cycle. That way, each connected component in the graph I built will have such a circle.

For each component we fake the circle, with a boy being the starting vertex, and then we erase the last edge in the cycle. Then I define the pairing like this: a boy will be paired with the girl in front of him in the cycle, and the opposite for girls.

This will give me the needed division. Is it good enough?

Answer 1

Yes, that works, but I would skip making/faking Eulerian cycles and just execute your idea directly:

1. If the list is empty, you're done. Otherwise, choose an arbitrary $(a, b)$ from your list, output it and remove it.

2. Find the unique $(c, b)$ in your list, output it and remove it.

3. If $(c, d)$ exists in the list, output it and remove it. Otherwise go to 1.

4. Find the unique $(e, d)$, output it, remove it, let $c \leftarrow e$ and go to 3.