We have two responses for you

Hi Amarjeet,

The condition i - j = 8 guarantees that sequence of vertices 1, 9, 17, ...97, 5, 13, ..., 1 is a cycle in the graph. There are three other such cycles (four cycles in total) because 4 is the greatest common divisor of 100 and 8. The length of each cycle is 100/gcd(100,8).

In a similar way, the condition i - j = 12 results in four (=gcd(100,12)) cycles of length 25 in the graph. The question becomes whether, for each of these, the vertices are all on the same cycle generated from i - j = 8. The sequence in the first paragraph contains the answer.

Victoria

You might try the following approach. Think of vertex 2; it can't be joined to any odd numbered vertex so the evens are in components by themselves (as are the odds). So, look at the even points only and change the problem from the points 2,4, ..., 100 with edges determined by differences of 8 and 12 to a smaller problem of vertices labeled 1, 2, ..., 50 with edges determined by differences of 4 and 6. Iterate.

Penny

Amarjeet wrote back

sir i am still not clear that either answer is 4 or 8. can you please help me out?

Hi again,

One cycle of length 25 is listed in my previous response. You can find another one that starts at vertex 2. then one starting at vertex 3, etc, until all of the vertices are in one of cycles you have. Try listing the
vertices for each of them in the same way as for the cycle containing 1. Each cycle is part of a connected component, so the number of components is at most the number of cycles. When the edges corresponding to i-j=12 are added to the graph, the number of components can not get larger. The only question is whether it gets smaller.

Victoria