Relatively prime graph solution

See the original problem

This is the solution I found:
N=105
M=6201

I tried searching for solutions for which N and M are odd.  That way I automatically get that 2 is a common factor of N+1, N-1, M+1, and M-1.

N needs to have a factor in common with M, M+1, and M-1.  Therefore, N needs at least 3 distinct prime factors.  N is odd, so the smallest N fitting this criteria is 3*5*7=105.

104 has prime factors 2 and 13.  106 has prime factors 2 and 53.  Therefore, M needs to have factors 13 and 53.  That is, M needs to be a multiple of 689.  The rest of my search consisted of trying different odd multiples of 689 until one worked.

There are many other methods to find a solution (and many other solutions), but that's mine.