Welcome to a lesson on isomorphic graphs.
Intuitively graphs are isomorphic
if they're basically the same, or better yet,
if they are the same
except for the names of the vertices.
To make the concept of renaming vertices precise,
we give the following definitions:
an isomorphism between two graphs G1 and G2
is a bijection f,
which maps V1 to V2
between the vertices of the graphs
such that a, b is an edge in G1
if and only if f of a, f of b is an edge in G2.
Remember, a bijection is a function
that is both one-to-one and onto.
Two graphs are isomorphic
if there is an isomorphism between them.
In this case, you write G1 is isomorphic to G2.
The symbol is also used for congruence in geometry.
An isomorphism is simply a function
which renames the vertices.
It must be a bijection
so every vertex gets a new name.
These newly named vertices
must be connected by edges precisely
when they are connected by edges with their old names.
Let's take a look at an example.
Decide whether graphs G1 and G2 are equal or isomorphic.
The graph G1 has vertices a, b, c, and d,
and edges a, b, a, c, a, d, and c, d.
The graph of G2 has vertices a, b, c, and d,
with edges a, b, a, c, b, c, and c, d.
Analyzing the edge sets
we can see the two graphs are not equal.
The set with elements a and d is in E1
and it's not in E2.
However, since both graphs
contain the same number of vertices
and the same number of edges,
they might be isomorphic,
this is not enough in most cases, but it's a good start.
A better start would be to analyze
the two graphs shown below.
You may want to pause the video
and verify these two graphs.
To verify the graphs,
we would verify the vertices and the edges.
Looking at the graphs
we should be able to determine an isomorphism.
So for the next step, we try to build an isomorphism.
To begin, let's just randomly state f of a equals b,
f of b equals c, f of c equals d,
and f of d equals a.
Defining f in this manner indicates
the function f maps the vertex of a
in V1 to the vertex b in V2,
it maps vertex b in V1 to vertex c in V2,
it maps vertex c in V1 to vertex d in V2,
and finally, the function maps
vertex d in V1 to vertex a in V2.
This is definitely a bijection,
but to make sure that the function is an isomorphism,
we must make sure it respects the edge relation.
To do this, we begin with the edge set E1
and apply the proposed isomorphism.
Applying the proposed isomorphism,
notice how we get the edge set b, c, b, d, b, a, and d, a.
Notice the b and the c in this first edge set came from
f of a and f of b.
The second edge set of b, d
came from f of a and f of c, and so on.
And now if we have an isomorphism,
this edge set must match the edge set E2.
And notice how we have a problem.
Notice the edge set under the proposed isomorphism
has the edge b, d,
and b, d is not an edge
in the graph of G2 or not an edge set in E2.
This indicates f is not an isomorphism.
Not all hope is lost, however.
Just because f is not an isomorphism
does not mean there is no isomorphism at all.
We can just try again.
At this point, it might be helpful to draw the graph
to see how they should match up.
And I would argue we should always stop
at looking at the graphs
to see how the vertices match up.
So analyzing the graphs of G1 and G2,
notice the vertex a in G1
matches up with vertex c in G2,
vertex b in G1 matches up with vertex d in G2,
vertex c in G1 matches up with vertex a in G2,
and vertex d in G1 matches up with vertex b in G2.
So now we'll build the bijection g,
which maps V1 to V2 by defining g of a equals c,
g of b equals d, g of c equals a,
and g of d equals b.
Now, I do want to mention
there may be more than one isomorphism.
And again, we need to check to see
if this really is an isomorphism.
It definitely is a bijection,
but we must make sure the edges are respected.
So again, the four edges in G1 are given by E1
and now we apply the proposed isomorphism,
which gives us the resulting edge set.
Notice c, d came from g of a, g of b;
c, a came from g of a, g of c and so on.
And now comparing the edge set
under the proposed isomorphism
to the edge set of G2 or the set E2,
notice, both contain the edge c, d,
both contain the edge c, a or a, c.
Remember the order doesn't matter.
Both contain the edge c, d or the edge b, c,
and both contain the edge b, a or the edge a, b.
The edges under the proposed isomorphism
are precisely the edges of G2.
Thus, g is an isomorphism,
and we say that G1 is isomorphic to G2.
I hope you found this helpful.