Project ForgeConsider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,j) : 1 ≤ i ≤ 12, 1 ≤ 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 __________.
Explanation
This is a 12×12 grid where each cell is connected to its "king-move" neighbours. The 4 corner cells have degree 3, the 40 remaining boundary cells (4×12−4 boundary cells minus 4 corners) have degree 5, and the 100 interior cells (144−44) have degree 8. Sum of degrees = 4(3)+40(5)+100(8) = 12+200+800 = 1012. By the Handshaking Lemma, edges = 1012/2 = 506.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.