Smallville is populated by unmarried men and women, some of which are acquainted. The two City Matchmakers know who is acquainted with whom. One day, one of the matchmakers claimed: "I can arrange it so that every red haired man will marry a woman with who he is acquainted." The other matchmaker claimed: "I can arrange it so that every blonde woman will marry a man with whom she is acquainted." An amateur mathematician overheard this conversation and said: "Then it can be arranged so that every red haired man will marry a woman with whom he is acquainted and at the same time very blonde woman will marry a man with who she is acquainted." Is the mathematician right?
Problem
Source:
Tags: graph theory, combinatorics unsolved, combinatorics
malcolm
08.06.2011 06:30
The mathematician is right. We will construct a matching satisfying his conditions. Consider a bipartite graph formed with the set of men from Smallville in one part, and the set of women in the other. For a matching arranged by the first matchmaker, colour an edge red between each red haired man and the woman he is matched with. Similarly, for a matching arranged by the second matchmaker, colour an edge blue between each blonde woman and the man she is matched with. Let $M$ and $W$ be the sets of vertices corresponding to red haired men and blonde haired women respectively, and $M'$ and $W'$ be the sets of vertices corresponding to of non-red haired men and non-blonde women respectively. Note there may be both a blue and a red edge between two vertices. Each vertex has degree at most $2$, hence through any vertex from $M$ or $W$ there exists a unique path (possibly a cycle) of maximal length, and the graph is a disjoint union of such paths. It suffices to find a matching satisfying the mathematician's conditions for each disjoint path. Consider one such path. If it is a cycle, it must be of even length since the graph is bipartite, and we simply choose every second edge of the cycle for our matching. If it is not a cycle, One of the endpoints of the path must be from $M'$ or $W'$, since if they are both from WLOG $M$, then the path has even length so one of the two endpoints has no red edge, and if one endpoint is from $M$ and the other from $W$, then the path has odd length so either the vertex from $M$ has no red edge or the vertex from $W$ has no blue edge, a contradiction. If the path has odd length, we may simply select every second edge starting from one of the endpoints for our matching and this will cover every vertex. If the path has even length, select every second edge starting from the endpoint opposite an endpoint which is from $M'$ or $W'$ for our matching. This will cover every vertex except an endpoint from $M'$ or $W'$, and in particular covers every vertex in the path which belongs to $M$ or $W$.