# 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 |
Okay, that was 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 |

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 *v*_{4} down to where *v*_{3} is and then move *v*_{3} up and to the right so that it's over *v*_{2} 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 *v*_{3} in the center graph corresponds to *u*_{3} 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 *v*_{1} and *v*_{4}, that the corresponding vertices in the other graph, in this case *u*_{1} and *u*_{4}, 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 *u*_{5} and *v*_{5} 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 *u*_{5} or *v*_{5}.