G in this problems was a graph Prove that if G is connected

G in this problems was a graph.

Prove that if G is connected and diam(G) greaterthanorequalto 3, then G is connected. Prove that if diam(G) greaterthanorequalto 3, then diam(G) lessthanorequalto 3 Prove that if G is regular and diam(G) = 3, then diam(G) = 2.

Solution

Solution:

a) Let V1,V2 be the vertex in V(G) satisfying d(V1,V2) >= 3. Then there must be an edge (V1 V2) in G\'. Now take another vertex U1 in V(G),if U1 is adjacent to V1,then d(U1,V1) >=2 & if it is not adjacent ,then edge (U1 V1) belongs to G\'.

So there must be a path in G\' through V1 V2 connecting all vertices U1 belongs i.e in V(G).Hence proved.

b) Proceed problem (a) ,Let\'s suppose U2 is any vertex in V(G), We either have a path U1V2V1U2 or U1V1V2U2 in G\' or have a path U1V1U2 OR U1V2U2 . So we can clearly see that in any case from U1 to U2 the distance is atmost 3. Hence proved.

c) In solution (b) , it is shown that if d(V1,V2) =3 in G ,then vertex U is adjacent in G\' to either V1 or V2. Now suppose G\' has N vertices ,so deg(V1) + deg(V2) >=N in G\' also G is regular ,so G\' is also & deg(V1) + deg(V2) >=N/2 for every U in G\'. Now pick any two vertices U1 U2, and N_j be the set of vertices whose distance from U_j is 0 or1 for all j = 1,2,

By considering the size of the sets N1 & N2 , we get |N1| + |N2|>=2 + 2*(N/2) =N+2.This more than all vertices in G\' , so there must be vertex U3 which is both in N1 and N2 .But d(U1,U2)<=2.

If diam(G\')=1 means that G has no edges that contradicts diam(G)>=3.So diam(G\')=2.Hence Proved.