It is obvious we can remove the "at most" condition and suppose that there are 4 other compatible species for each specie. Consider the graph of $K_8$ with 3 edges at each node removed so that in total we remove 12 edges. The degree of each node is even, so we can find an euler circuit through this graph. Label the nodes A..H. The circuit looks something like ABCB... where we write each letter 2 times. Taking every two adjacent letters (where the first and last are considered adjacent) , we find we have 16 'adjacencies'. Every adjacent pair of letters is a legal pair. Since we never use the same edge twice in a circuit, we have all 16 legal pairs. Since we use all edges in a circuit, the following method is guaranteed to work: we take our 'circuit string' and pick any pair in it, and erase all the letters that the pair uses. We repeat this 3 more times. Each stage, we are guaranteed to find a pair, because the string necessarily contains all pairs formed of unused letters. The 4 pairs are our solution. Example: AEBFCGDHCEDFAGBH; pick AE BFCGDHC DF GBH; pick GB FC DHC DF H; pick DF C HC H; pick HC and done.

Singular wrote: Each stage, we are guaranteed to find a pair, because the string necessarily contains all pairs formed of unused letters. The 4 pairs are our solution. Why is that? I don't understand. Can anybody explain?

Sorry for the reply to an old topic. Isn't the problem a direct conseguence of Dilworth's Theorem?

I think we can generalize it into $2n$ and $n$ ccases,where $3$ is replaced with $n-1$.

Singular wrote: It is obvious we can remove the "at most" condition and suppose that there are 4 other compatible species for each specie. Consider the graph of $K_8$ with 3 edges at each node removed so that in total we remove 12 edges. The degree of each node is even, so we can find an euler circuit through this graph. Label the nodes A..H. The circuit looks something like ABCB... where we write each letter 2 times. Taking every two adjacent letters (where the first and last are considered adjacent) , we find we have 16 'adjacencies'. Every adjacent pair of letters is a legal pair. Since we never use the same edge twice in a circuit, we have all 16 legal pairs. Since we use all edges in a circuit, the following method is guaranteed to work: we take our 'circuit string' and pick any pair in it, and erase all the letters that the pair uses. We repeat this 3 more times. Each stage, we are guaranteed to find a pair, because the string necessarily contains all pairs formed of unused letters. The 4 pairs are our solution. Example: AEBFCGDHCEDFAGBH; pick AE BFCGDHC DF GBH; pick GB FC DHC DF H; pick DF C HC H; pick HC and done. I also find this a bit too optimistic Take the following circuit for eg: 4-5-1-2-5-3-1-6-7-8-2-7-6-4-3-8 we can remove 1-2 first, then 3-4, then we are left with 5 5 6-7-8 7-6 8 where 5 can never be paired with anything It appears this algorithm is not at all intuitive and will need at least a 1-ply look-ahead to work properly,

actually 6 and 7 doesn't satisfy the problem requirement in my previous example, a correct example would be: 4-5-1-2-5-3-1-6-7-8-2-7-3-4-6-8 again remove 12, then 34, and 5 is left hanging