GATE CS 2014 Set 1 Q51 — Graphs: Connectivity, Matching, Colouring

The vertices of the graph $G$ can be visualized as a $12 imes 12$ grid. An edge exists between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$ (excluding self-loops). This means two vertices are connected if they are adjacent horizontally, vertically, or diagonally.

We can count the total number of edges by classifying them into four categories:

• Horizontal edges: Each of the $12$ rows contains $11$ horizontal edges.
  $\text{Count} = 12 \times 11 = 132$
• Vertical edges: Each of the $12$ columns contains $11$ vertical edges.
  $\text{Count} = 12 \times 11 = 132$
• Diagonal edges (top-left to bottom-right): Each of the $11 \times 11$ grid squares of size $1 \times 1$ contains exactly one such diagonal.
  $\text{Count} = 11^2 = 121$
• Diagonal edges (bottom-left to top-right): Similarly, each of the $11 \times 11$ grid squares contains one such diagonal.
  $\text{Count} = 11^2 = 121$

Summing these up gives the total number of edges: