GATE 2014 CS (CS1) – Question 61
An undirected graph without self-loops has vertices $\{(i,j):1\le i\le12,\ 1\le j\le12\}$. Distinct vertices (a,b) and (c,d) are adjacent when $|a-c|\le1$ and $|b-d|\le1$. Find its number of edges.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 506 to 506
Explanation
Horizontal edges number12×11=132, and vertical edges also132. Each of11×11unit cells has two diagonal edges, adding242. Total **506edges**. Counting these four orientations avoids double-counting undirected edges; self-loops are explicitly excluded.