What is a selection protocol for choosing from n teams so all teams play k other teams?

Question

Note: this problem is similar to this previous question but this aspect of the query was not fully addressed there.

First, if $n$ is even, $k$ can be any value from 1 to $n-1$. If $n$ is odd, then $k$ can be any even value from 2 to $n-1$.

I would like a selection (accumulation or depletion) protocol to randomly select $k$ teams for each of the $n$ possible teams so that all $n$ teams play $k$ games, and no team plays any other given team more than once.

¿Does anyone know of a protocol to achieve this?

Addendum: A student and I have been working on this a bit, and we thought that one strategy would be to iteratively cull the network of edges connecting all teams (of which there are $\frac{n^2-n}{2}$ edges). Using a possible games that might be played matrix (a matrix representing the existing edges), one could randomly select a home team from the complete list of teams, then select an away team from the remaining list that aren't also in the list of already played teams, then remove these two teams from the possible choices and make the next selection. Graphically, it was removing one of the remaining edges, and then dropping all edges with those two teams from the next step in the culling process.

Any assistance would be gratefully welcomed.

---

Update #1

We now know that our protocol fails. If we start with six teams, $\{A,B,C,D,E,F\}$, we start with the complete edge network (all teams playing all other 5 teams), we start by randomly selecting home and away teams from the remaining teams, and this edge is removed (thus these teams won't play each other).

Here's an example of the protocol breaking down in 2 steps:

1. Step 1, A&B are removed, then C&D, then E&F
2. Step 2, A&C are removed, then B&D, but there are only two teams left, E & F, and they can't be removed, because they already have been removed

My background in combinatorics is very weak, so even the most basic comments may help us toward a solution or a reasonable work-around.

Answer 1

Here is a simple method. We start with zero edges, and add edges until everyone has $k$ edges.

If $k$ is even$\dots$

1. Choose a permutation of the $n$ peoples. Call this permutation $[a_1,a_2,\dots,a_n]$.

2. Check to see if any of the edges $\{a_1,a_2\},\{a_2,a_3\},\dots,\{a_{n-1},a_n\},\{a_{n},a_1\}$ have been added in a previous step.

   • If any of the edges were previously added, then throw them all out, and return to step $1$.

   • If none of the edges have been previously added, then add them all in. This adds two edges to every person. If everyone currently has $k$ edges, you are done. If not, return to step $1$.

If $k$ is odd (which necessarily means that $n$ is even), then you should start by choosing a random perfect matching of the people, and add in all of those edges. This gives everyone one edge, so now you can proceed to step $1$, adding two edges per person at a time until $k$ are reached.