Explore BrainMass

Connected Graphs

Let G be a graph of diameter at least three. Can you find an upper bound on the diameter of the complement of G? Prove your findings!

Let G be a connected graph and sq(G) be a graph which contains all vertices and edges of G and moreover edges joining every pair of vertices that were in G at distance 2. In other words, xy is an edge of sq(G) if and only if the distance of x and y in G is at most 2. Prove that sq(G) is 2-connected.


Solution Summary

Connected graphs are investigated.