The difference between a graph and its square

Abstract

For a graph G, its square G² is the graph with the same nodes, where two nodes in G² are connected if their distance is at most 2 in G. By examining the connected components of the 2-step graph, G² - E(G), we establish n - 2 as a lower bound on the number of edges added to G when G² is formed, and provide examples to illustrate the tightness of this bound.