Sudoku Graph

Each element of the grid cannot be the same as any other element in the same row, column, or $3 \times 3$ box. There are $8$ such elements in the same box and $6$ other elements each in the same row and column. Therefore, each vertex of the graph has $20$ edges coming from it, and since each edge touches two vertices, there are a total of $\frac{1}{2} \times 20 \times 81 = \boxed{810 \text{ edges.}}$

w.r.t @Henry Maltby solution, it is reminiscent of the sum of arithmetic series if you just look at a row, the # edges = 8 + 7 + ... + 1 = (9*8)/2 = 36. As you connect the first node to the next 8, the next node does not need to connect to the first node, just the next 7.

Apply this to the whole sudoku:

You get the idea... Notice that for every cell, you can pair it with a compliment s.t. the 2 cells sum to 20, i.e. cell (1,1) + cell(9,9) = 20 + 0 = 20, cell (1,2) + cell(9,8) = 19 + 1 = 20 ... Therefore, since every cell has a compliment, s.t. the sum = 20, then 20 * 81 / 2 = 810 edges.

Another way of thinking about it, you can superimpose an inverted sudoku and add the superimposed sudoku with its respective cell from the original, you would get something like this:

20+0, 19 + 1, 18 + 2 | 17 + 3...

17 + 3...

the result would be:

20, 20, 20 | 20...

20...

hence, if you sum all the cells -> 20 * (# of cells) = 20 * 81 = 1620 however, the sum must be divided by 2 since we added the superimposed sudoku, 1620 / 2 = 810 edges.

It is similar to the arithmetic concept of adding 1 + 2 + 3 + ... + n = (n(n+1))/2

1 + 2 + 3 = 6 - line 1

3 + 2 + 1 = 6 - line 2

sum line 1 and line 2

line 1 + line 2 -> (4 + 4 + 4) = 12 then divide by 2 to remove the addition of line 2 ----> (n(n+1))/2 = (3*4)/2 = 6