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

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 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.

Here is an example of two non-isomorphic graphs $G$ and $H$ with isomorphic 2-step graphs $G^{(2)}$ and $H^{(2)}$.
• That's great, thanks! Any chance you can adapt your example so that $G$ and $H$ are connected? – Paul Siegel Jul 23 '14 at 22:28
• On further consideration I realized that your example doesn't quite work: the isolated vertex in $G^{(2)}$ has a self edge with weight $3$ while the isolated vertex in $H^{(2)}$ has no self edge. But the example has nevertheless been food for thought... – Paul Siegel Jul 27 '14 at 22:24