####
**Question:**

Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {i,f): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if |a -c 1| ≤1 and

b d 1 − ≤ The number of edges in the graph is _____________.

**Solution:**

**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**

## No comments:

Post a comment