GATE CSE 2014 Set 1 | Question: 51

Question

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______.

Comments

@Tuhin Dutta very nice diagrammatic representation. Thank you...

---

nice explaination

---

Answer is 506. 

A clear explanation of the solution is in this image. I hope everything will be cleared. I tried to show every detail of every edge.

 

 

Answer 1

There are already some great answers here, just adding my 2 cents on finding the recurrence relation for this question. Let $E_n$ denote number of edges in the given graph with $n$ vertices. Then given a graph with $k-1$ vertices, we can add edges systematically to it to make it a graph with $k$ vertices as follows:

1. Add $2k-3$ “crosses” (one cross next to each of the $k-2$ crosses already present and one at the corner giving us $2(k-2) + 1=2k-3$)
2. Add $2(k-1)$ horizontal edges
3. Add $2(k-1)$ vertical edges

This gives us the recurrence relation : $E_n = E_{n-1} + \underbrace{2(2k-3)}_{\text{crosses}} + \underbrace{2(k-1)}_{\text{horizontal edges}} + \underbrace{2(k-1)}_{\text{vertical edges}}$

 

Below is the visualization when going from graph with 2 vertices to graph with 3 vertices :

Notice that in the base case, $E_2=6$

Answer 2

SO total- 506