Question

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

• A. 506

Answer 1

The correct option is A 506
The given condition translates into the graph shown below where every vertex is connected only with its neighbours.

From above diagram:
(i) The four corner vertices have each 3 degrees which gives 4 × 3 = 12 degrees.
(ii) The 40 side vertices have 5 degrees each contributing a total of 40 × 5 = 200 degrees.
(iii) The 100 interior vertices each have 8 degree contributing a total of 100 × 8 = 800 degrees.

So total degree of the graph
12 + 200 + 800 = 1012 degrees

Now the number of edges in any undirected graph
$=\frac{\text{Total degrees}}{2}$

Therefore the number of edges in this graph
$=\frac{1012}{2}=506$