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)
```