Pair Arrangement Problem During Holiday meal we were thinking about a problem.
To simplify a real world case, let's say each couple of married parents have 2 children which are also married.
Each couple of parents want both their children to be with them in the holiday.
children must come with their spouses.
So they should come one year to one parents and the other year to the other parents.
The marriages between children are random.
How can we get a solution to this problem, is there a similar problem already discussed in the past.
Of course there won't be a solution all the time because the connection can be circular.
 A: Thanks to these assumptions:


*

*clear distinction between children and parents (i.e., there are no grand parents),

*each parent couple having exactly 2 children,


you can reduce your problem to the ordinary matching problem.
Make a graph where vertices are the parents couples (one vertex per couple), and for each child or spouse shared between parents couples we add an edge. A solution for this problem is possible if and only if the graph is bipartite. Here is a simple odd-cycle counterexample:
$$
\mathrm{parents\ pairs} = \{AB, CD, EF\}\\
\mathrm{children\ pairs} = \{bc, de, fa\}
$$
where couple $XY$ have children $x$ and $y$.
If parent couple $AB$ gets both children in year $1$ (that is, both $bc$ and $fa$), then no other parent couple can do this the same year. But then, in year $2$, only one of $CD$ and $EF$ can have both their children together.
On the other hand, if the graph is bipartite, then you can color each parent couple red or blue, and then red parents get their children on odd years and blue parents get their children on even years.
For arbitrary number of children you can solve your problem using the vertex-coloring where each color denotes the year on which these parents get their children (and the number of necessary colors is the minimum cycle-period in years). In particular we know that if the graph has maximum degree $d$, then $d+1$ colors suffice (in your simplified case it means that you can always make an arrangement over 3-year period).
I hope this helps $\ddot\smile$
