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

If you think of a $12\times 12$ grid (like a chess board of size $12\times 12$), then each each point $\left(i,j\right)$, which is in $i^{\text{th}}$ row and $j^{\text{th}}$ column, is a vertex $\left(i,j\right)$.

Now we are allowed to connect only those points which are atmost $1$ distance apart (in both horizontal and vertical direction). So we will connect only horizontal neighbours, vertical neighbours, and diagonal neighbours.

So horizontal edges on each row are $11$ i.e. $11\times 12 = 132$ horizontal edges. Similarly we have $132$ vertical edges.

To count diagonal edges, think of $1\times1$ square boxes in which diagonals meet each other. There are $11\times 11$ such square boxes, and each box contains $2$ diagonals, so total diagonals $= 242$.

So total edges $= 132 + 132 + 242 = 506.$

Comments

nice explanation @Happy mittal

---

The Condition mentioned in the question is :

If |a−c|≤1AND |b−d|≤1

Dont u think edges are only along diagonals because both conditions should be satisfied. If the condition were having OR instead of AND then your answer was correct..

Please correct me if I am wrong

---

it is exceptional thinking

Answer 2

Total number of vertices $= 12\times 12 = 144.$

The graph formed by the description contains $4$ (corner) vertices of degree $3$ and $40$ (external) vertices of degree $5$
and  $100$ (remaining) vertices of degree $8.$

 According to (handshake theorem's)

$2|E|=$ sum of the degrees

$ 2|E| = 4\times 3+40\times 5+100\times 8= 1012.$

$|E| = \frac{1012}{2} = 506$  edges.

Comments

@Mithlesh Upadhyay
But , the 4 corner edges are - (1,1),(12,1),(12,12) and (1,12). Here (12,1) and( 1,12) are same. Rest all others are same. But (1,1) and (12,12) are not same. Please see into it.

---

Love this approach

---

what a nice explanation @Mithlesh Upadhyay, thanks a lot

 

Answer 3

There will be ‘11’ edges in a horizontal line, so for 12 horizontal lines, 11×12=132
There are ‘11’ edges in vertical line, so for 12 vertical lines, 11×12=132
There are ‘2’ diagonals ‘⊠’ in each square box.
There are 11×11 square boxes available. So 11×11×2=242
------------------------------------------
Total: 132+132+242
=506 edges

Comments

11*11*2 not 12 please correct it..

Answer 4

Given:
The vertex set of G is {(i, j): 1 <= i <= 12, 1 <= j <= 12}.
There is an edge between (a, b) and (c, d) if |a − c| <= 1 and
                                              |b − d| <= 1.

There can be total 12*12 possible vertices. The vertices are (1, 1),
(1, 2) ....(1, 12) (2, 1), (2, 2), ....

The number of edges in this graph?
Number of edges is equal to number of pairs of vertices that satisfy
above conditions. For example, vertex pair {(1, 1), (1, 2)} satisfy
above condition.

For (1, 1), there can be an edge to (1, 2), (2, 1), (2, 2). Note that
there can be self-loop as mentioned in the question.
Same is count for (12, 12), (1, 12) and (12, 1)

For (1, 2), there can be an edge to (1, 1), (2, 1), (2, 2), (2, 3),
                                    (1, 3)
Same is count for (1, 3), (1, 4)....(1, 11), (12, 2), ....(12, 11)

For (2, 2), there can be an edge to (1, 1), (1, 2), (1, 3), (2, 1),
                                    (2, 3), (3, 1), (3, 2), (3, 3)
Same is count for remaining vertices.

For all pairs (i, j) there can total 8 vertices connected to them if
i and j are not in {1, 12}

There are total 100 vertices without a 1 or 12.  So total 800 edges.  

For vertices with 1, total edges = (Edges where 1 is first part) +
                    (Edges where 1 is second part and not first part)   

                                =  (3 + 5*10 + 3) + (5*10) edges

Same is count for vertices with 12

Total number of edges:
= 800 + [(3 + 5*10 + 3) + 5*10]  + [(3 + 5*10 + 3) + 5*10]
= 800 + 106 + 106
= 1012

Since graph is undirected, two edges from v1 to v2 and v2 to v1
should be counted as one.

So total number of undirected edges = 1012/2 = 506.