Skip to main content
1 of 4
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

From equivalent graphs to isomorphic one- Reconstruction Conjecture

Suppose we are working with connected simple graphs.

We say two graphs $G$ and $H$ are equivalent 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$ and $H$ are equivalent, then they are isomorphic?

The motivation of this question goes back to the reconstruction conjecture. I want to say that if the reconstruction conjecture is true for $G$, then it is true for all graphs which are equivalent to $G$.

Shahrooz
  • 4.8k
  • 1
  • 24
  • 36