Skip to main content
2 of 4
added 8 characters in body; edited title
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

From semi-equivalent graphs to isomorphic one- Reconstruction Conjecture

Suppose we are working with connected simple graphs.

We say two graphs $G$ and $H$ are semi-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$, or vice versa.

Can we say that if $G$ and $H$ are semi_equivalent, then they are isomorphic?

The motivation of this question goes back to the reconstruction conjecture. I want to say that if the two graphs $G$ and $H$ are semi-equivalent and RC is true for one of them, then is true for other one.

Shahrooz
  • 4.8k
  • 1
  • 24
  • 36