Are these two graphs isomorphic? Why/Why not?

Question

Are these two graphs isomorphic?

---

According to Bruce Schneier:

"A graph is a network of lines connecting different points. If two graphs are identical except for the names of the points, they are called isomorphic."

^{Schneier, B.  "Graph Isomorphism"
From Applied Cryptography
John Wiley & Sons Inc.
ISBN 9780471117094}

---

According to a GeeksforGeeks article:

These two are isomorphic: And these two aren't isomorphic:

^{Manwani, C. "Graph Isomorphisms and Connectivity"
From GeeksforGeeks
https://www.geeksforgeeks.org/mathematics-graph-isomorphisms-connectivity/}

---

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."

^{Weisstein, Eric W. "Isomorphic Graphs."
From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/IsomorphicGraphs.html}

---

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.

Please try to keep answers as clear and simple as possible for the sake of understanding.

"Truth is ever to be found in the simplicity, and not in the multiplicity and confusion of things."

–Isaac Newton

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

I think the thing here that you are missing that from the only thing in the definition of the graph are the vertices and the edges (in the general case; there are other, more specialized graphs). So the only thing we should take from the visual representation of the grap are - the vertices and the edges.

So even though visual representation of a graph might have other properties like direction, dimension (2d or 3d representation), interjections, angles or edge-lenghts we should ignore them. What this means is that while dealing with a visual representation of a graph, we can move the points around in any dimension (keeping the edges intact), rotate the graph or stretch the edges and the graph stays the same. Not only are the graphs isomorphic, they are actually the same graph (apart from the different named vertices).

It might help to work out the actual definitions of said graphs by hand as described by Theo Bendit and see for yourself that there is nothing different in graphs one and two, unlike in graphs three and four.

Answer 5

What is a "graph"?

So you're reading through some math about data structures and whatnot and you just can't seem to wrap your head around what a "graph" is exactly. You've graphed functions on graph paper as far back as secondaryschool and had no trouble with it, but now the little "lines and dots" diagrams you keep seeing pop up in the explainations of "trees" and "cycles" and "edges" just seems to have no connection to what you've learned before about graphing. You see something like the following:

And it just seems to make no sense - it is as if the "graphs" have no care at all for the postion or scaling or orientation of the lines and points on the page!

There is a good reason for that. The dots and lines on the page is just a symbolic sketch of what the "graph" represents. The lines on the page have nothing to do with the "y=mx+b" equations you'd graphed in secondary school, and neither do the dots have anything to do with cartesian coordinates you may have plotted on those same pieces of graph paper. Instead, what is being represented on the page is the simple existance of a number of veritices (the dots) and the existence of connections between specific vertices (the lines); the actual "graph" itself being the abstract idea of a certain number of objects having a certain number of connections between them arranged in a specific way. Other than historical precedent, there isn't really any need for them to be called "graphs", nor for them to be pictorally represented by lines and dots. It's basically just because most textbook writers and textbook readers have meat-brains that are generally intuitive about 2D and 3D space that we keep this pictoral shorthand around. Computers would rather just be sent an easy-to-parse list of vertex objects and vertex connections, like the following:

(where we have ordered everything alphaneumarically for our own conveniance; though that fact is not required at all). In fact, one could systematically order every possible pairing of points and assign a binary 1/0 to the presence or lack of the corresponding connection (in practice that get messy as the number of possible connections scales approximately with O[n^2] while sparse matrices will more reasonably grow around O[n] connections).

So what does all this have to do with your question? Well, it lets us explain why we can poke and prod at the dots and lines in our "meatspace" symbolic diagrams and still get a logical comparison of similarities and differences between two abstract "graphs". Even though things look remarkably transformed in "meatspace", the relations go unchanged in "listspace" and thus the abstract objects themselves go unchanged despite all the cosmetic "meatspace" changes we've used to simplify the correspondence (or lack thereof) between multiple objects.

Is Pentagon-A isomorphic to Pentagram-B?

How would we go about this problem? Well, first we could look at the two graphs in "meatspace" to see if it's super straightforward (like comparing a square to a rectangle). Then if that doesn't work, we can look in "listspace" to see if anything is simpler there.

In this case, both "meatspace" and "listspace" don't do us any favors. Our pictoral diagram has way more confusing crossings in one picture versus the other, and in our list our default alphaneumeric ordering is doing us no favors. We could try brute-forcing the list by assigning b1=a1 and then assign b2=a2 and on down the line until something breaks and we try a different combination of assignments (like a really inefficient Sudoko puzzle), but perhaps there's a way to simplify things in meatspace instead.

We can now use this relation to find way to compare A directly to B. If one then plugs a1->b1, a2->b3, etc. into the A-list to get a B'-list.

Comparing the B list to the B' list, every vertex and every specific vertax-to-vertex connection occurs the exact same number of times. They're isomorphic!

This isn't the only way we could go about it, though. Instead of simplifying things in "meatspace" we could try to simplify things in "listspace". What if we noticed that both shapes can be drawn "without taking your pen off the paper", then we could come to the conclusion that if there is a long a1-to-a2-to-a3... path through the list of connections in A, then the two can only be isomorphic if there is an equivalent path through the Bs. Instead of listing connections alphaneumerically, we could instead try listing a connected chain of entries:

Making a "longest chain" through our entries appears to work really well for this pair of examples. The pentagon has a very simple chain a1-a2-a3-a4-a5-a1 that loops back on itself, and the pentagram also loops back on itself with the b1-b3-b5-b2-b4-b1 which also loops back on itself. Both loops are 5-connections long, and there are no other chains or side loops to worry about. They must be isometric!

But wait! Everything seems to work out no matter what we do. What if we plug just any old thing in for the ai->bj conversion?

Well, if we accidentaly guess 3/5 of the correct answers (relative to our other worked out example) then we get something like...

and clearly our guess did something wrong, because two specific connections are missing from B' and two extra connections exist where they aren't supposed to be; indicating that this ai->bj conversion was not an isomorphic mapping. So, clearly brute-forcing can hit bad answers.

Are these two hexagons with two extra edges isomorphic?

So now that we have a bunch of tools and tricks to fiddle around with these abstract "graph" things, how about those two examples with 6-points and 8-edges each?

Well, on the one hand, we can push and prod until we have no more crisscrossing happening in "meatspace", then we have a set of three quadrangles (and everything else outside) on our B side; but on the A side we have two triangles, one quadrangle, and everything else outside. That doesn't line up correctly with the other pictogram no matter how we rotate our hexagon.

If we try to go from "listspace" instead, then we can try the "longest chain" trick again and get a 6-gon with two extra connections, but there is no way that we can reorder things such that the two remaining connections in A' have anything to do with the two remaining connections in B'. If, instead we try to make a minimal chain, then we have 3-loops {a1,a2,a6} and {a3,a4,a5} which we cannot recreate in any way with the 4-loop minimums of {b1,b2,b3,b6}, {b3,b4,b5,b6}, etc.

In fact, 6-vertices is not too much that every 6! possible mapping from ai->bj could be tested in a reasonable amount of time to show that the graphs in fact have no working mappings, and thus they cant be isomorphisms of one another.

Answer 6

Disclaimer

This answer is an excuse to show an animation that a 5-year-old might understand. If you're looking for correct mathematical definitions, please switch to other answers or Wikipedia.

Definitions

First, please be careful not to confuse:

• a graph and the representation of a graph
• a graph and a chart.

Isomorphism

In layman terms, two graphs are isomorph if there is a continuous movie transforming the representation of a graph into the other:

It is allowed to drag and rename vertices, it is not allowed to add or cut edges. The movie acts as an edge-preserving bijection, which is how graph isomorphism can be defined.

Here's the online tool I used.

Non-Isomorphism

The second example is here.

By dragging around vertices, you cannot create the triangles ($b,c,d$ or $a,e,f$) that are present in the other graph:

From a logical point of view, it isn't enough to show one failed attempt in order to prove that something isn't possible. To prove that the graphs aren't isomorph, you could count their cliques.