These two graphs look different but are they from a graph theory point of view structurally the same?

If you look closely you see that they are structurally the same.

They are the same up to the renaming of the vertices.

In fact, we can define a function that renames the vertices of the first graph as in the second graph. These graphs are isomorphic.

The renaming function f is an isomorphism.

Formally G1 and G2 are isomorphic if there is a bijection f on V1 to V2

with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are

adjacent in G2 for all a and b in V1. Function f is called

isomorphism.

An isomorphism f preserves edges, thus preserving properties of graphs that depends on edges.

That means cycles and degrees are preserved.

It's often easy to show that two graphs are not isomorphic.

For instance, if they have a different number of vertices or edges or if the degree of the vertices does not match up.

But showing that they are isomorphic

requires that an isomorphism can actually be produced which is much harder.

For instance, look at these two graphs.

The orange graph has two vertices of degree 3 while the blue graph does not, so they are not isomorphic.

How about these two? Can you find an

one-to-one and onto function to map all vertices of one graph to the other one?

And these two?

Same number of vertices, same number of edges, same number of vertices of each degree, but...

If these two graphs are isomorphic then a must correspond to

either t, u, x, or y.

t, u, x, and y all have a neighbor with degree 2 which is not true for a, so they are not isomorphic.

But why should we want to know whether two graphs are isomorphic?

What sort of problem can be solved? Any ideas? Share them with us and others in the forum.