Consider an undirected graph \(G\) where self-loops are not allowed. The…
2014
Consider an undirected graph \(G\) where self-loops are not allowed. The vertex set of \(G\) is \(\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}\). There is an edge between \((a,b)\) and \((c,d)\) if \(|a-c| \leq 1\) and \(|b-d| \leq 1\). The number of edges in this graph is______.
Attempted by 165 students.
Show answer & explanation
Correct answer: 506
Concept: In a simple undirected graph, the number of edges can be found in two independent ways: (1) the Handshaking Lemma — the sum of all vertex degrees equals twice the number of edges, i.e. Σdeg(v) = 2|E| — or (2) direct counting, by adding up the adjacent pairs along each distinct direction of adjacency without double-counting any pair.
Application (Handshaking Lemma method):
Model the 144 vertices (i, j), 1 ≤ i, j ≤ 12, as cells of a 12×12 grid. Two vertices (a,b) and (c,d) are adjacent exactly when |a−c| ≤ 1 and |b−d| ≤ 1 (excluding the vertex itself) — this is "king-move" adjacency, i.e. up to 8 neighboring cells.
Corner cells (4 of them: the four corners of the grid) each touch only 3 neighbors (two orthogonal + one diagonal), so each has degree 3. Contribution: 4 × 3 = 12.
Border, non-corner cells: 10 such cells on each of the 4 sides = 40 cells. Each touches 5 neighbors (two along the border + three toward the interior), so each has degree 5. Contribution: 40 × 5 = 200.
Interior cells: (12−2) × (12−2) = 10 × 10 = 100 cells. Each touches all 8 surrounding neighbors, so each has degree 8. Contribution: 100 × 8 = 800.
Sum of degrees = 12 + 200 + 800 = 1012.
By the Handshaking Lemma, number of edges = 1012 / 2 = 506.
Cross-check (independent direction-wise count):
Horizontal edges (same row, adjacent column): 12 rows × 11 adjacent pairs per row = 132.
Vertical edges (same column, adjacent row): 12 columns × 11 adjacent pairs per column = 132.
One-direction diagonal edges, i.e. (i,j)–(i+1,j+1) pairs: 11 × 11 = 121.
Other-direction diagonal edges, i.e. (i,j)–(i+1,j−1) pairs: 11 × 11 = 121.
These four directions are mutually exclusive and together cover every adjacent pair exactly once, so total edges = 132 + 132 + 121 + 121 = 506 — confirming the direction-wise method covers all cases with no double-counting, and matches the Handshaking Lemma result.
Both independent methods agree: the graph has 506 edges.