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.


EDIT: This answer assumes a path cannot contain repeated edges or vertices. The OP is interested in the case where edges and vertices can be repeated. See comments below.

Here is an example of two non-isomorphic graphs $G$ and $H$ with isomorphic 2-step graphs $G^{(2)}$ and $H^{(2)}$.


  • $\begingroup$ That's great, thanks! Any chance you can adapt your example so that $G$ and $H$ are connected? $\endgroup$ – Paul Siegel Jul 23 '14 at 22:28
  • $\begingroup$ I don't see any way to modify this example to make both graphs connected. I thought for a few minutes and did could not come up with a connected example. I'll let you know if I am able to find one. $\endgroup$ – John Machacek Jul 25 '14 at 19:57
  • $\begingroup$ Your example resolves this question as I asked it (and I could not produce a disconnected example on my own) so I posted the connected case as a separate question: math.stackexchange.com/questions/878575/…. $\endgroup$ – Paul Siegel Jul 26 '14 at 7:42
  • $\begingroup$ 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... $\endgroup$ – Paul Siegel Jul 27 '14 at 22:24
  • $\begingroup$ What is your definition of path? It sounds like you are allowing edges to be repeated? So, in that case every vertex will have a self edge (loop) in the 2-step graph with weight equal to the degree of the vertex? $\endgroup$ – John Machacek Jul 27 '14 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.