number of edges in a graph

Question

I got a problem related to graph theory -

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

Answer is given as 506 but I am calculating it as 600, please see attachment.

I am unable to get why it is coming as 506 instead of 600.

Thanks

Answer 1

For a grid in the range of $[n_1,n_2]$, according to the problem statment, the number of edges is:

$$\#edges=\frac{8 \times (n_2-n_1+1)^2- 4\times 5-4\times3\times(n_2-n_1-1)}{2}$$

explanation: suppose every node has a degree of 8, then sum of the degrees is $8\times(n_2-n_1+1)^2$; For each corner we included 5 extra edges that must be removed (the term $4\times5$) and for every other border node we considered 3 more edges (the term $4\times3\times(n_2-n_1-1)$).

The solution for your problem is:

$$\frac{8(12-1+1)^2-4(5)-4\times3\times(12-1-1)}{2}=\frac{8(144)-20-12(10)}{2}=\frac{1012}{2}=506$$

Answer 2

Method 1

This is one kind of problem you can write a program to solve instantly. We are counting the number pairs satisfying the conditions you state. First generate the vertices (I'm using Python).

vertices = []
for x in range(1, 13):
  for y in range(1, 13):
    vertices.append([i, j])

Next count the pairs satisfying the conditions.

count = 0
for p in pts:
  for q in pts:
    if p != q:
      a, b = p
      c, d = q
      if abs(a - c) <= 1 and abs(b - d) <= 1:
        count = count + 1

Every edge has been counted twice, hence the answer is count / 2.

Method 2

There are four types of edges: vertical, horizontal, diagonal (slope 1 and -1). Observe that the number of vertical edges is equal to the number of horizontal edges and the number of slope -1 diagonal edges is equal to the number of slope 1 diagonal edges. So the total number of edges is 2 * #vertical + 2 * #diagonal.

The number of vertical edges is $11\times 12=132$. The number of diagonal edges is $2\times(1+2+\dots+10)+11=121$. $132\times 2 + 121 * 2 = 506$. This can be generalized to a square grid of any size: if the $1\le i,j\le n$, then the number of edges is $$2(n(n-1) + (n-1)(n-2) + (n-1)) = 2(n-1)(2n-1)$$.

Plug $12$ in the formula and you get $506$.

Answer 3

This is simple math no need to generalize any folrmula.

condition type1 :a=c

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

total combinations satisfying condition1 : 12

total combinations satisfying condition2 : 11 (I am taking only one case either a-c=1 or c-a=1 .Think about it why?)

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

visit : http://yougeeks.blogspot.in/2015/01/consider-undirected-graph-g-where-self.html#more

Answer 4

Total number of vertices $= 12*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*3+40*5+100*8= 1012$

$|E| = 1012/2 = 506$ edges.