Comparing Graphs, Part I

At some point every branch of mathematics comes up with a way to determine if two things are somehow the same. In arithmetic it's called "equality". In geometry it's called "congruence". Graph theory borrows its word from algebra: isometric.

The technicalities start to get a little deep in this sectoin and the next one. Don't let that discourage you. These sections aren't absolutely essential to the rest of the subject so don't let them keep you from pressing on.

What You Should Learn

  • What it means for two graphs to be the same.

Let G1 and G2 be two graphs. The two graphs are isomorphic if there is a one-to-one function, f, from V(G1) to V(G2) such that if two vertices, u and v, are adjacent in G1 then f(u) and f(v) are adjacent in G2. If f is an isomorphism from G1 to G2 then the inverse function, f-1 , is an isomorphism from G2 to G1.

Okay, that was really technical but the idea behind it is simple. Remember that the idea behind being "isometric" is that the graphs have to be the same. The definition says that we're going to call two graphs "the same" if we can pair the vertices in one graph with the vertices in another so that if two vertices in one graph are connected, then the vertices with which they're paired are also connected. We'll look at several examples of this below that should make this more intuitive.

Before we do that look at the last sentence - the part where it talks about an inverse function. All this means is that isomorphism goes both ways: If G1 is isomorphic to G2 then G2 is isomorphic to G1.

Look at the three graphs below. Which of them are isomorphic? Remember in the very first section I told you that the position of the points didn't matter. The only thing we care about in graph theory are how the points are conneced? This idea is at the heart of isomorphism. If you can reposition the vertices of one graph so that it's identical to another then they are isomorphic. If you take the middle graph and push v4 down to where v3 is and then move v3 up and to the right so that it's over v2 you'll get something identical to the left hand graph but with the u's replaced with v's. Because we can make the two graphs look the same, without removing any of the edges or adding any new ones, they must be isomorphic. If you want to look back at the formal definition we have to pair the vertices in the first graph with the vertices in the second. You can do this by matching the numbers, for example v3 in the center graph corresponds to u3 in the left hand graph. (This will not always be the case. Sometimes the numbers will be jumbled.) You should confirm for yourself that if you pick any two adjacent vertices from one graph, for example v1 and v4, that the corresponding vertices in the other graph, in this case u1 and u4, are also adjacent.

So what about the graph on the right? It turns out that it isn't isomorphic to either of the other two. Showing that two graphs are not isomorphic can be a trick. In this case, we have an easy way out that will lead directly into the next section. Notice that u5 and v5 both have degree 3, i.e. they are each connected to three other vertices. Because there is no vertex in the graph on the right that is connected to three other vertices there is no way the graphs can be isomorphic. No matter how you try to reposition the vertices in the right hand graph you will never be able to find one that matches the "shape" of u5 or v5.

Comparing Graphs, Part II >><< Broken Graphs, Exercises