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.

4more comments