# Is a connected graph uniquely determined by its weighted 2-step graph?

This is an extension of a previous question: https://math.stackexchange.com/questions/876336/is-a-graph-uniquely-determined-by-its-weighted-2-step-graph/876357#876357. In that question I asked about arbitrary graphs; in this question I restrict to connected graphs. Here are the details:

Let $G$ be an undirected graph. Define the 2-step graph $G^{(2)}$ of $G$ to be the weighted graph whose vertices are the same as those of $G$ but whose edges correspond to 2-step paths in $G$. Thus the weight of an edge $(u,v)$ is the number of distinct vertices $w$ such that $(u,w)$ and $(w,v)$ are both edges in $G$. (In particular, the weight of $(u,u)$ is the degree of $u$ for every vertex $u$.) My question:

Are there two connected, non-isomorphic graphs $G$ and $H$ such that $G^{(2)}$ is isomorphic to $H^{(2)}$?

My intuition says that the answer should be "yes", but I'm unable to construct an example.

• You would like an example with simple graphs, I assume? – Studentmath Jul 26 '14 at 8:07
• @Studentmath Yes. – Paul Siegel Jul 26 '14 at 8:14
• If connected graphs were so easily determined, the isomorphism problem for them would be decided in polynomial time --- but that's widely believed to be impossible, so surely there are counterexamples. – Gerry Myerson Jul 26 '14 at 8:53
• Correct me if I am wrong, but this is equivalent to asking whether two different irreducible, 0-1 matrices may have the same equivalent $A^2$ matrix? – Studentmath Jul 26 '14 at 8:56
• @GerryMyerson Do you have a specific polynomial time algorithm in mind for determining whether or not the $2$-step graphs are isomorphic? As far as I can tell the isomorphism problem for the $2$-step graphs is just as hard (maybe harder?) than the isomorphism problem for the original graphs. – Paul Siegel Jul 26 '14 at 15:10

A counterexample can be constructed as follows. Let $G$ be the graph of a hexagonal pyramid and $H$ be that of a pair of tetrahedra sharing one common vertex. Then, $G^2$ and $H^2$ are isomorphic while $G$ and $H$ themselves are not. Indeed, $G$ has a simple $6$-cycle but $H$ has not.