134k views
5 votes
What is an example of two graphs that are isomorphic but their
spanning trees are not.

User Indre
by
7.9k points

1 Answer

4 votes

Final answer:

Two isomorphic graphs with a square arrangement of vertices and different diagonals as edges can have non-isomorphic spanning trees due to the choice of edges included in the spanning trees.

Step-by-step explanation:

A student asked about an example of two isomorphic graphs whose spanning trees are not isomorphic. First, let's understand that two isomorphic graphs have a one-to-one correspondence between their vertices and edges, preserving adjacency. However, the structure of their spanning trees can differ due to the multiple spanning trees that a graph can have.

Here is a simple example to illustrate this. Consider two separate graphs, both with four vertices arranged in a square. In one graph, the edges form a square with one diagonal (graph A), while in the other graph, the edges form a square with the opposite diagonal (graph B). The graphs are isomorphic because there is a one-to-one correspondence between their vertices and edges. However, when looking at the spanning trees, graph A can have a spanning tree that includes the diagonal, while graph B cannot. If we consider the shape formed by the edges of the spanning trees, one will have a triangle with an extension (in graph A) and the other will simply be a path or a 'T' shape (in graph B).

Therefore, while the original graphs are isomorphic, their spanning trees can be non-isomorphic due to different choices of edges.

User PhilHoy
by
8.2k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories