Graph isomorphism

A graph is a collection of dots (called vertices) joined by curve segments (called edges). It doesn’t matter how you name the vertices and it doesn’t matter where you put them in your drawing. Two graphs are called isomorphic if you can rearrange the way one of them is drawn to make it look like the other. So for example you might convince yourself that a pentagon and pentagram are isomorphic to each other.

Untitled

In this discussion we built graphs out of pipe cleaners and tested isomorphisms by hand. Of course an isomorphism can always be demonstrated physically. But how can you demonstrate the absence of an isomorphism? We found lots of properties of a graph (called invariants) which are preserved by isomorphisms. If two graphs have different invariants, then they can’t be isomorphic!

Check out this very fun graph isomorphism puzzle online!

Our handout for the discussion.