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

Satisfying conditions for |a -c 1| ≤1

 1.  condition type1 :a=c

2.   condition type2: a-c=1 or c-a=1.

 total number of pairs (a,c) satisfying condition1 : 12
 total number of pairs (a,c) satisfying condition2 : 11

so satisfying combinations for 'a' and 'c' = 11+12 =23

IN Similar way satisfying combinations for 'b' and 'd' = 23

[ a     b]
      *
[ c     d]

So total solutions = 23*23 = 529

Now there are some cases where loop exists
like :
[1,2]             [5,5]
[1,2]   OR    [5,5]

There will be 23 such cases .Why ?? :)

So remove such cases : 529-23 = 506
http://yougeeks.blogspot.com/2015/01/consider-undirected-graph-g-where-self.html

Comments

Won't there be 144 self loops?

Answer 2

Generalised formula for any i=j=n ->

1) Total no of horizontal edges = (n) *(n-1)

2)Total no of vertical edges = (n) *(n-1)

3) remaining are cross edges . If we consider 1 small square box , 2 cross edges

there are total (n-1)*(n-1) small boxes

so total no of cross edges = 2*(n-1)*(n-1)

Ans So total no of edges = 2* (n) *(n-1)  +  2(n-1) *(n-1)

Here n=12

So total no of edges = 2*12*11  +  2*11*11 = 264+ 242 = 506

Answer 3

(1,1 ), (1,12), (12,1),(12,12) will have degree = 3

(1,x),(x,1),(12,x),(x,12) will have degree = 5

2<=x<=11

Remaining will have degree = 8

Total (1,x) =10

Similarly (12,x) = 10

Total (x,1)= 10

Similarly (x,12) = 10

Remaining = 144-40-4= 100

Sum of degree = 2* Edges

4*3+ (10+10+10+10)*5 + 100*8 = 2* Edges

1012=2* Edges

Therefore, edges= 506

Answer 4

Answer : 506

2|E| = Sum(Degree)   // we add all the edges twice while counting degree so , this formula is valid in any connected graph

2|E| = (10*10*8) + (4*3) + (40*5)

2|E| = 1012

|E| = 506