3 Let GVEbe the graph given by V12 100 and E x ygcdx y 1 a

3. Let G=(V.E)be the graph given by V=(1.2 100) and E = {(x, y)|gcd(x, y) = 1). (a) Prove that G is connected. (b) What is diam(G)?

Solution

a)Let G be a graph

   with V={1,2,3-------100}

         E={(x,y)|gcd(x,y)=1}

let take vertexes 1,2; gcd(1,2)=1

  and take vertexes  2,3; gcd(2,3)=1

and take vertexes  3,4; gcd(3,4)=1

and take vertexes  4,5; gcd(4,5)=1

-----------------------------

---------------------------------

----------------------------------

and take vertexes   99,100; gcd(99,100)=1

so that from above

   edges among all vertexes.

so that we can called this connected graph(G).

b)Digm(G) mapping stores the isomorphism mapping of G.