Create a "pairing" from a graph?

Question

This problem smells like there should be an answer in graph theory, but it doesn't exactly match any of the graph theory problems I know. (Note: this is actually a real-world problem, fictionalized for easier reading)

Imagine that I have a even-numbered group of Chess players at my house. I have plenty of tables and chess sets for everyone to play, but I need to create a "Pairing," (not sure if there is a graph theory term for it) or a list of matchups such that everyone plays someone. The chess players would all like to play someone they have never played before.

If I have a list from each player of who they have played, I can easily construct a graph showing previous matchups. For example, say A has played B and C, and C has played D:

A----B
|
|     
C----D

I know that I can match up B/C and A/D to create a pairing.

But if the graph of previous matchups looks like this:

A----B
  \  |
   \ |
C    D

Then I will not be able to create a pairing. B can only play C, which would make A and D (who have already played) play each other.

So, how can I know (via some method other than brute force) whether or not I can create a pairing? It's not a tree or a cycle that I'm looking for, but is there some other graph property I can test for?

Answer 1

Looks like the classic matching problem: en.wikipedia.org/wiki/Matching_(graph_theory). What you are probably looking for is a perfect matching.

Also look at: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm

Note: in order to use the matching algorithm, you need to use the Complement of the graph you describe in the question.

Answer 2

If you were to represent every player in your graph twice, once coloured red and once coloured green (say, but avoiding black and white to avoid confusion with chess pieces) this might turn into a problem on a bipartite graph for which there are oodles of resources.