3
$\begingroup$

I am trying to under isomorphism in graphs, and from what I know, if graph A is isomorphic to graph B, then you could basically just rearrange the nodes in A, while keeping the edges connected the same, and get graph B. But I found a question and answer from the internet here:

http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf

Question 1.1.34

here is a screen shot below, and the three sub graphs shouldn't be isomorphic. For example, the first graph has 2 nodes of degree 3 and the other 2 don't.

Can someone explain this?

Thanks

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ It should be mentioned, that two graphs are isomorphic if and only if there exists a way you can move vertices from the first graph around (dragging edges with them) and relabel them to make it look exactly like the second graph, but finding such a way to drag things around is usually quite difficult. It is much easier to show that they aren't isomorphic using invariant qualities about the graph (such as number of vertices of particular degree like you mention). It is unknown if the general problem is P, or NP complete. en.wikipedia.org/wiki/Graph_isomorphism_problem $\endgroup$
    – JMoravitz
    Jan 26 '15 at 13:28
4
$\begingroup$

Each of the three pictures they show are of completely different decompositions. Restrict your attention for the moment to just the far left image.

petersongraph

In this graph, they have colored the edges three ways (in the original picture as thick lines, thin lines, and dashed lines).

If you look at each color class individually, they are all isomorphic to the shape shown below. They are saying that for the peterson graph, you can find a decomposition such that all three subsets of the edges are isomorphic to the same subgraph (which are furthermore symmetric according to rotation), and give three different examples of such decompositions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.