# Doofish Matrix -- Graph approach

I have tried using the Edge coloring of a complete graph.

This problem turns into one of the special cases ( The case [r=2] ) of Baranyai’s theorem.

As it can be proved that there’s no solution for odd (`N > 1`), this problem comes into “class one” graphs according to Vizing’s theorem . I have tried to implement it in `O(N^2)` but sadly didn’t succeed. Has anyone approached this problem using Graphs and came up with an efficient solution?

For example

consider `N = 6`

As we need `2N -1` groups

``````(i > j) --> (N-1)

(i = j) -- > 1

(i < j) --> (N-1)
``````

and the `(i < j)` part of the matrix is

``````(1,2)(1,3)(1,4)(1,5)(1,6)

(2,3)(2,4)(2,5)(2,6)

(3,4)(3,5)(3,6)

(4,5)(4,6)

(5,6)
``````

Consider a graph with 6 vertices and above 15 pairs as edges (complete graph ) we need to divide these 15 pairs into 5 `(N -1)` groups (coloring) such that all 6 numbers occur in each group.

5 - coloring

`````` (1,2) (3,4) (5,6)
(1,3) (2,5) (4,6)
(1,4) (2,6) (3,5)
(1,5) (2,4) (3,6)
(1,6) (2,3) (4,5)
``````
3 Likes

I think you are looking for Round-Robin Tournaments.

3 Likes

exactly, this might be the author’s intention.

1 Like