Создать “соединение” из графика?

Эти проблемные запахи как должны быть ответом в теории графов, но она точно не соответствует ни одной из проблем теории графов, которые я знаю. (Отметьте: это - на самом деле реальная проблема, беллетризованная для более легкого чтения),

Предположите, что у меня есть четная группа Шахматистов в моем доме. У меня есть много таблиц и шахмат для всех для проигрывания, но я должен создать "Соединение", (не уверенный, если существует термин теории графов для него), или список матчей, таким образом, что все играют кого-то. Шахматисты все хотели бы играть кого-то, кого они никогда не играли прежде.

Если у меня есть список от каждого игрока того, кого они играли, я могу легко создать график, показывающий предыдущие матчи. Например, скажите, что A играл B и C, и C играл D:

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

Я знаю, что могу подойти B/C и A/D для создания соединения.

Но если график предыдущих матчей похож на это:

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

Затем я не смогу создать соединение. B может только играть C, который сделал бы A и D (кто уже играл), играют друг друга.

Так, как я могу знать (с помощью некоторого метода кроме грубой силы), могу ли я создать соединение? Это не дерево или цикл, который я ищу, но являюсь там некоторым другим свойством графика, на которое я могу протестировать?