How to find n-1 complete matches for bipartite graphs that are related (speed-date)? How can one assign n people pairwise to n-1 tables, in a speed-date fashion, such that no two persons meet twice and each person is at each table exactly once? Does this problem have a name?

The problem in full

Given n people (n is even), assign them in pairs in n-1 rounds. Each round represent a list of n/2 pairs, each pair being two individuals that have not met earlier.

For each round, find a match between the n/2 pairs and n-1 tables, so that every pair are assigned a table. The tables are unique. Through all n-1 rounds, an individual should meet each other individual exactly once, and be at each table exactly once.

What have I tried?

Here is the naive bipartite matching algorithm I've created so far:


Create rounds using the round-robin tournament scheduling.
Represent each round as a bipartite graph, pairs vs tables.
For each round, find a match.


For each player, remove table matched in this round.



In pseudo:

n = 6
tables = [1, 2, 3, 4, 5]
players = [{'i': 1, 'tables': copy(tables)}, {'i': 2, 'tables': copy(tables), ...]
rounds = roundRobin(players)
# each round has a list of pairs
# each pair is two players
# [ 
#     [[1,6], [2,5], [3,4]], 
#     [[1,2], [3,6], [4,5]], 
#     ...
# ]
matches = []
# keep matches

for round in rounds:
    match = hopcroft_karp(round, tables)
    # pair 1 to table 1, ...
    # [ [1, 1], [2, 2], [3, 3] ]

    if len(match) !== len(round):
        # TODO: backtrack
    else:
        add match to matches
        for edge in match:
            pair = round[edge[0]]
            table = edge[1]
            removeTable(pair[0], table)
            removeTable(pair[1], table)


Example

For some n, there is no solution. For example n = 4. I'm unsure for which n the problem has solutions. Here is n = 4 as an example:

People: 1, 2, 3, 4
Tables: A, B, C

Round 1: A:1,2 - B:3,4
      In round 1, we can assign tables at random, because
      the problem is the same with renaming tables.
Round 2: C:1,3 - ?:4,2 &lt;-- not possible
      4 has already been at table B. 
      2 has already been at table A. 
      Table C is taken by pair 1,3.
Round 3: ?:1,4 - ?:2,3 &lt;-- same as round 2
Your problem seems to be the same as that of constructing a Room square. Let me quote from The existence of Room squares by Mullin and Wallis:

A Room square of side $2n+1$ is a $2n+1$ by $2n+1$ array of cells and a set $S$ of $2n+2$ objects called symbols which satisfy the following conditions:
(i) Every cell of the array is either empty or contains an unordered pair of distinct symbols from $S$.
(ii) Each symbol occurs in every row and column of the array.
(iii) Every unordered pair of symbols occurs precisely once in the array.

Mullin and Wallis state that a Room square of size $v$ exists for all odd positive $v$ except for $v=3,5$. This explains why your construction for $n=4$ (which corresponds to $v=3$) wasn't successful.
To construct a Room square, look into the article Construction of Room Squares by Stanton and Mullin.