Degree of freedom paradox for a rigid body

You've duplicated constraints because if any one particle is constrainined in all three dimensions with all the other particles this constrains all the particles. The number of constraints is 3(N - 1).

To give an example, take three particles a, b and c. If a is fixed relative to b and is also fixed relative to c, then b and c are fixed relative to each other without having to introduce new constraints.

Each particle that makes up a mechanical system, can be located by three independent variables labelling a point in space.

You can choose any particle in the rigid body to start with and move it any where you want, giving three independent variables needed to specify its location.

Choosing a second particle, you choose another set of three independent variables to specify its location, the obvious being spherical coordinates with the origin at the first particle. The first constraint is that the radius is a constant, leaving two remaining independent variables.

Choosing a third particle, you have complete freedom to rotate it by any angle about the axis through the first and second particles giving just one degree of freedom, the other two variables constrained.

For the remaining (N-3) particles, all three coordinates are constrained.

Therefore, the total number of degrees of freedom for a rigid body is 3+2+1 = 6, with 0+1+2+3(N-3) = (3N-6) constraints.

So that the degrees of freedom becomes 3N - (3N-6) = 6

The problem is that you are double counting a lot of your constraints. If the (vector) displacements between particles A and B, and between B and C is fixed, then the displacement between A and C is fixed. Therefore the constraint on distance between A and C is redundant, and you can't count it separately.