Maximum number of diverse interactions between sets within a closed network

Question

I have multiple networks where the edges between the nodes need to be drawn in a way that satisfies the following characteristics:

• Network needs to be closed in the sense that each node needs to have a link to another node, and each node needs to be a target for another node (no node can have a link to itself).
• A node can have a maximum one link to another node.
• There are multiple sets of nodes, and ideally there is maximum diversity in terms of connectedness between sets within the network. Meaning that ideally, each node has a link to a node from a different set.

Here is an illustration:

Network with two sets

Now, my question is: How to calculate the maximum number of edges between nodes that point to another set? In case of two sets - as in the example above - the answer is the number of nodes in the smallest group times 2 i.e. in the case above 4.

However, I'm not sure how this can be extrapolated to other configurations e.g. where there are multiple sets, such as below:

Network with three sets

In that case the answer is 9 i.e. the total number of nodes. But of course this is not a rule; if we have 2 sets each with a single node and there is the third one with 10 nodes, the answer is 4.

Answer 1

Suppose there are $n$ nodes. Let $m$ be the maximum number of nodes in any one color. Say the maximum color is red.

If $m>n/2$, then you can have at most $2(n-m)$ edges. This is because there are at most $2$ edges for each non-red node: one going in, the other going out. This is attainable by pairing each non-red node with a red node like $\bullet \longleftrightarrow \bullet$, and then arbitrarily connecting the remaining red nodes.

If instead $m\le n/2$, then you can ensure all $n$ edges go between nodes of different colors as follows:

1. If there are two colors with $n/2$ nodes in each color, you can achieve $n$ edges by pairing up oppositely colored nodes. In what follows, assume this is not the case.

2. If $n$ is even, set aside one of the nodes whose color appears the most. The remaining $n-1$ nodes will still have the property that no one color is a strict majority. Let the number of remaining nodes be $n'$, so $n'$ is odd.

3. Arrange the remaining nodes in a line, so same colored nodes appear contiguously. Call the nodes in this order $V_1,V_2,\dots,V_{n'}$.

4. Arrange the nodes in a circle in the order: $$ V_1,V_{(n'+3)/2},V_2,V_{(n'+5)/2},V_3,V_{(n'+7)/2},\dots,V_{(n'-1)/2},V_{n'},V_{(n'+1)/2} $$ where $V_1$ wraps around to be next to $V_{n'-1}$. For example, when $n'=9$, this looks like $V_1,V_6,V_2,V_7,V_3,V_8,V_4,V_9,V_5$. This circle has the property that adjacent nodes are different colors.

5. If there was a node set aside in step 2, then insert somewhere in the circle so that it is not next to any nodes of its color. This is possible since that color is not a strict majority.

6. Once all the nodes are in a circle, connect each node to its clockwise neighbor.

For example, if there were $5$ red, $4$ yellow, and $3$ green nodes, then you would first set aside a red node, line up the remaining nodes like $$ \mathrm{R\;R\;R\;R\;Y\;Y\;Y\;Y\;G\;G\;G} $$ and then put them in a circle like $$ \mathrm{R\;Y\;R\;Y\;R\;G\;R\;G\;Y\;G\;Y} $$ and finally stick the set aside $\mathrm R$ between the last $\mathrm G$ and $\mathrm Y$.