How to find connected components of a random graph?

If you are given a G-square graph, how can you find all the connected g graphs for that particular G-square graph?

• A g-square graph of a given connected undirected graph 'g' is defined as the given graph g + we need to add an edge between any pair of vertices of g  whose distance between them is exactly 2.

• Answer:

  This is just my analysis after taking a first look at the question, I do not know the correct solution.   This question of finding a g-graph given a g-square graph is essentially asking me to de-triangulate the given graph. Identify the triangles in a graph and remove either of the connecting edge out of three edges. It might seem trivial that for every triangle, I have two choices so total number of g-graphs from given g-square graph can be 3 times no of triangles. But the situation becomes bit tough when you have triangles in graph sharing an edge. Like one shown in fig1. You can de triangulate graph by removing single edge bd.  Or if we tried removing any other edge, we need to remove either ad bc, ad dc, dc ab, ab bc – 4 possibilities. Possibilities change when we have figure like one on right side in fig2. So the point it is bit vague to ask all the graphs which can give me a given g-square graph, the combinatorial bound is not that intuitive or I am not aware of it if it exists. If it asks me just to find any g-graph given a g-square graph then it becomes simple. Use any traversal say BFS, keep a hop count of number of hops to reach a given vertex for each predecessor. For a vertex of degree n, I will have n values since I can reach it through n vertices. When I encounter vertex again during traversal, check its previous hop count if it differs by one with current hop count, you can check if you can reach current parent from this vertex by one and remove it. You can detriangulate in time it takes for a breadth first search traversal. This will give you any g-graph for a given g-square graph but asking for all the g-graphs seems bit too much. There might be solution for this that I am not aware of and I am excited to see other responses on this.