Skip to main content
3 of 4
added 22 characters in body
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

From NS-equivalent graphs to isomorphic one- Reconstruction Conjecture

Suppose we are working with connected simple graphs.

We say the graph $G$ is NS-equivalent to $H$ (NS stands for non-symmetric) if for any spanning tree $T_G$ in $G$ there is an spanning tree $T_H$ in $H$ such that $T_G$ is isomorphic to $T_H$.

Can we say that if $G$ is NS-equivalent to $H$, then they are isomorphic?

The motivation of this question goes back to the reconstruction conjecture. I want to say that if we have $G$ is NS-equivalent to $H$ or vice versa, and RC is true for one of these graphs, then it is true for other one.

Shahrooz
  • 4.8k
  • 1
  • 24
  • 36