Are two graphs isomorphic if: every spanning tree of one graph is isomorphic to some spanning tree of the other, and vice versa?

109 Views Asked by At

Let $G_1,G_2$ denote two simple graphs, and $T_1,T_2$ denote their respective set of all spanning trees. Are $G_1,G_2$ isomorphic if every $t \in T_i$ is isomorphic to some $t' \in T_j$ for both $i,j \in\{1,2\}$? How do you prove or disprove this?

1

There are 1 best solutions below

0
On BEST ANSWER

Both statements are wrong.

  1. Every spanning tree of graph $C_3$ is $P_3$ (a simple path of order 3). Exactly the same spanning tree has $P_3$.

  2. Consider a graph $G$ with vertices $V(G)=\{1,2,3,4\}$ and edges $E(G)=\{12,23,13,34\}$. This graph has spanning trees of two types: $T_1=G-12$, $T_2=G-13$.