4
$\begingroup$

Suppose we are working with connected simple graphs.

We say the graph $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$ and vice versa.

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 $G$ and $H$ are equivalent and RC is true for one of these graphs, then it is true for other one.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Based on its MR review, Sedláček - The reconstruction of a graph from its spanning trees says no; but I can't find the original article. $\endgroup$
    – LSpice
    Commented Jan 9, 2021 at 22:30
  • 3
    $\begingroup$ @LSpice The article is here. $\endgroup$
    – Jeremy Rickard
    Commented Jan 9, 2021 at 22:49
  • 2
    $\begingroup$ Your question seems to ask whether two equivalent-in-your-sense graphs are isomorphic, and the answer (by Sedláček's article) is that they need not be. $\endgroup$
    – LSpice
    Commented Jan 9, 2021 at 23:03
  • 2
    $\begingroup$ While @bof's comments on terminology are certainly apposite, surely this isn't what you meant. If you really wanted this asymmetric relation, then it is easy to come up with counterexamples: just take $H$ a non-tree, and $G$ a spanning tree of $H$. Surely what you meant was to consider the case where each spanning tree of $G$ is isomorphic to a spanning tree of $H$, and vice versa (possibly with multiplicity)? Anyway, the counterexample of Sedláček is a counterexample to this stronger condition. $\endgroup$
    – LSpice
    Commented Jan 9, 2021 at 23:40
  • 4
    $\begingroup$ a cycle is equivalent to a path with the same number of vertices $\endgroup$
    – Fedor Petrov
    Commented Jan 9, 2021 at 23:52

1 Answer 1

Reset to default
7
$\begingroup$

The following counterexample, with two finite, connected graphs in which every tree occurs as a spanning tree with the same multiplicity but that are not isomorphic, is given in Sedláček - The reconstruction of a graph from its spanning trees (thanks to @JeremyRickard for the link): Two graphs that are 'equivalent' but not isomorphic

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .