Yrurtj

Are these two graphs isomorphic?

According to a GeeksforGeeks article:

These two are isomorphic:

And these two aren't isomorphic:

<sup>Manwani, C. "Graph Isomorphisms and Connectivity"

From GeeksforGeeks
https://www.geeksforgeeks.org/mathematics-graph-isomorphisms-connectivity/</sup>

According to a MathWorld article:

"Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic."

<sup>Weisstein, Eric W. "Isomorphic Graphs."

From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/IsomorphicGraphs.html</sup>

The details are beyond me, but the MathWorld explanation seems to conflict with the first GeeksforGeeks example; the vertices appear the same, but they appear to be connected differently.

To add to the confusion, the same could be said for the second example. So I can't really deduce the facts.

Both claims are correct.

Mapping $$e_1 to c_1, qquad e_2 to c_3, qquad e_3 to c_5, qquad e_4 to c_2, qquad e_5 to c_4$$ maps the edges of the left graph precisely to those of the right graph, so that map defines an isomorphism of graphs.

The right graph has cycles of length $3$ (e.g., $aefa$) but he left graph does not, so the graphs cannot be isomorphic.

Here's something important to keep in the back of your mind when studying graphs: the definition of a graph. There are actually a few deviations in how one can define a graph, but this one will suffice for our purposes:

A (simple) graph $G$ is an ordered pair of set $(V, E)$ (the sets of vertices and edges respectively), where $E$ consists of subsets of $V$ of cardinality $2$.

When the graph is finite (meaning $V$, and hence $E$, is a finite set), we can visually represent a graph by a diagram, assigning each point from $V$ to a distinct point in $Bbb{R}^2$ (or occasionally, $Bbb{R}^3$). If ${u, v} in E$, then we draw a path from the point representing $u$ to the point representing $v$, going through no other point representing a point in $V$.

These diagrams are what we often tell people are "graphs", but they are really just a way to represent graphs. The first diagram represents the graph:
$$G_1 = ({e_1, e_2, e_3, e_4, e_5},{{e_1, e_2},{e_2, e_3}, {e_3, e_4}, {e_4, e_5}, {e_5, e_1}}).$$
The second diagram represents the graph:
$$G_2 = ({c_1, c_4, c_2, c_5, c_3},{{c_1, c_4},{c_4, c_2}, {c_2, c_5}, {c_5, c_3}, {c_3, c_1}}).$$
(Note the leading way in which I've decided to order the elements of my sets in defining $G_2$!)

Note that, if we took the picture of $G_1$ and, say, rotated it (keeping all the labels), then that picture would represent the same graph $G_1$. Not something isomorphic to $G_1$, I mean it would have exactly the same vertex and edge sets, i.e. the graph it represents would literally be $G_1$, even though it's a new picture. You could even start moving the vertices around independently of each other (again, keeping the same labels), and the diagram will continue to represent $G_1$.

In this way, we see that there is an enormous variety of diagrams to represent exactly the same graph.

Further, it is possible for multiple graphs to produce the same diagram (except with different labels on the vertices). If you draw, for example, $G_2$, with $c_1$ in the same position as $e_1$, $c_4$ where $e_2$ was, $c_2$ where $e_3$ was, $c_5$ where $e_4$ was, and $c_3$ where $e_5$ was, and connected up the adjacent vertices with line segments, it would come out to be the same diagram as the one for $G_1$, with different labels.

In that sense, we see that $G_1$ and $G_2$ are structurally the same graph, even though they share no vertices or edges! So, pictures introduce unnecessary variety through muddling up the positions of vertices, and the set definition of graphs introduce unnecessary variety by allowing label substitutions which don't affect the actual structure of the graph. How do we talk about two graphs being the same, in a way that doesn't throw up a false negative when the points are moved or renamed?

Enter, stage left, the concept of a graph isomorphism. If we have graphs $(V_1, E_1)$ and $(V_2, E_2)$, a graph isomorphism is a bijection $f : V_1 to V_2$ with the property that ${v, w} in E_1 iff {f(v), f(w)} in E_2$. So, the function preserves adjacency.

Two graphs are "the same" when an isomorphism exists between them. The isomorphism deals purely with the set definition of graphs (and hence doesn't care how you draw them), but will still exist even if you rename the vertices. We can therefore see that $G_1$ and $G_2$ are isomorphic, with an isomorphism as described above. The way I wrote $G_1$ and $G_2$ exposes this isomorphism clearly as well.

How can you tell that the other pair of graphs is not isomorphic? I think Travis covers this well in his answer. In the graph on the right, there are three vertices, e.g. $b, c, d$, such that any pair of them is an edge in the graph, i.e. ${b, c}, {c, d}, {b, d}$ are elements of the edge set. If an isomorphism $f$ existed, there would need to be points $f(b), f(c), f(d)$ such that ${f(b), f(c)}, {f(c), f(d)}, {f(b), f(d)}$. No such points $f(b), f(c), f(d)$ exist in the first graph (via quick exhaustive search), so no isomorphism exists. This implies that there's no way to rearrange the vertices from one diagram (and change their labels) to form the other diagram.

Summary (or tl;dr):

• Graphs are defined using sets, not pictures!


• The same graph may be drawn in many ways, so don't get distracted by vertices moving!


• Isomorphisms don't care about the names of the vertices or their positions.


• To see why the first pair are isomorphic, but the second pair aren't, see Travis's answer.

The definition you quoted from MathWorld is too simplistic. Two graphs are isomorphic if there is some way to match up the vertices of one with the vertices of the other, so that the connections by edges are also matched up. The desired matching might not match vertices that are in the same positions in some drawings (for example, the top vertex in one picture need not match with the top vertex in another picture), nor does it necessarily match up vertices with similar-looking labels (like $v1$ and $v1'$). Any one-to-one correspondence between the vertices of one graph and the vertices of another graph is a candidate for an isomorphism --- a successful candidate if the edges then also match up. Travis's answer has given you an appropriate correspondence between the pentagon and the $5$-pointed star. You should check that it really works, i.e., that whenever two vertices of the pentagon are joined by an edge then (and only then) the corresponding vertices of the star are joined by an edge in the star.

A side comment: The fact that any one-to-one correspondence might serve as an isomorphism (if the edges match up correctly) is what makes it non-trivial to check whether two large graphs (i.e., graphs with many vertices and edges) are isomorphic. It's an open problem whether this checking can be done by an algorithm in a number of steps bounded by a polynomial function of the number of vertices. There has, however, been important progress recently; Babai has given an algorithm that's way more efficient than the brute force approach of checking all possible one-to-one correspondences.