[Solved]: number of edges in a graph

Problem Detail: 

I got a problem related to graph theory -

Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, d) if |a-c|<=1 and |b-d|<=1 The number of edges in this graph is

Answer is given as 506 but I am calculating it as 600, please see attachment.

I am unable to get why it is coming as 506 instead of 600.

Thanks

Asked By : codeomnitrix

Answered By : emab

For a grid in the range of $[n_1,n_2]$, according to the problem statment, the number of edges is:

$$\#edges=\frac{8 \times (n_2-n_1+1)^2- 4\times 5-4\times3\times(n_2-n_1-1)}{2}$$

explanation: suppose every node has a degree of 8, then sum of the degrees is $8\times(n_2-n_1+1)^2$; For each corner we included 5 extra edges that must be removed (the term $4\times5$) and for every other border node we considered 3 more edges (the term $4\times3\times(n_2-n_1-1)$).

The solution for your problem is:

$$\frac{8(12-1+1)^2-4(5)-4\times3\times(12-1-1)}{2}=\frac{8(144)-20-12(10)}{2}=\frac{1012}{2}=506$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23532