Question 61

The graph $G$ consists of vertices $(i, j)$ for $1 \le i, j \le 12$, forming a $12 \times 12$ grid with $144$ vertices.
An edge exists between $(a, b)$ and $(c, d)$ if $|a - c| \le 1$ and $|b - d| \le 1$ (excluding self-loops).

Let us count edges by category:

1. Horizontal edges:
   Each of the 12 rows contains $12 - 1 = 11$ horizontal edges.

   $$\text{Horizontal edges} = 12 \times 11 = 132$$

2. Vertical edges:
   Each of the 12 columns contains $12 - 1 = 11$ vertical edges.

   $$\text{Vertical edges} = 12 \times 11 = 132$$

3. Diagonal edges:
   The grid has $(12 - 1) \times (12 - 1) = 11 \times 11 = 121$ unit squares.
   Each unit square contains 2 diagonal edges:

   • One leading diagonal (slope $+1$)
   • One trailing diagonal (slope $-1$)
   $$\text{Diagonal edges} = 2 \times 121 = 242$$

Total number of edges in $G$:

Verification via Handshaking Lemma:

• 4 corner vertices each have degree 3: $4 \times 3 = 12$
• $4 \times 10 = 40$ boundary non-corner vertices each have degree 5: $40 \times 5 = 200$
• $10 \times 10 = 100$ interior vertices each have degree 8: $100 \times 8 = 800$