# Are these two graphs isomorphic? Why/Why not?

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

• First of all, are you clear on the definition of isomorphic? – Mike Mar 9 at 19:24
• You are not using definitions. Two things are isomorphic given an isomorphism, but you don't give one. Lacking one, common sense suggests "isomorphic" means for some isomorphism of a given kind. For graphs "isomorphic" assumes a certain kind of isomorphism. You are misusing descriptions that are too vague to be definitions. You quote MathWorld, but the explicitly informal introductory description, not the definition. Find formal definitions of "isomorphism" & "isomorphic". Also you seem to confuse the picture of a graph with the graph it pictures. Find a formal definition of "graph". – philipxy Mar 10 at 4:11
• Words have meanings. You need to learn them. There is no royal road. "Explain like I was five" is said by people not willing to put in the effort to understand presentations they already found. This post is just asking, what does it mean for two graphs to be isomorphic, without any research effort--see the voting arrow mouseover texts. If you are stuck in some presentation(s) you should ask about where you are stuck, not ask for yet another one. You quote paraphrasings that are clearly from their context not definitions. They're useless. If you didn't know already, now you do. – philipxy Mar 10 at 9:50
• Let's just say that @philipxy is completely right. The first sentence in the MathWorld article is merely an attempt at a gloss of the meaning of graph isomorphism, and not a precise statement. The precise definition is given in the second sentence, which you didn't even quote in your question! – user21820 Mar 10 at 10:13
• I'm voting to close this question because I don't think that it is about mathematics as it is currently phrased. To be about mathematics, the objects being described need to be rigorously defined. For example, the terms "graph" and "graph isomorphism" have not been properly defined. – Xander Henderson Mar 10 at 12:21

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.

• So, are the first two graphs isomorphic or not? – tjt263 Mar 10 at 6:04
• @tjt263 Yes. We can use many mappings. This one doesn't require much rearranging to see that it works: e1 -> c5, e2 -> c2, e3 -> c4, e4 -> c1, e5 -> c3; visually, you can move c1 to below c4 and c3 to below c5 to get the same shape as the left graph. – jaxad0127 Mar 10 at 6:18
• @jaxad0127 but isn't the whole idea of isomorphism, that it doesn't have to be rearranged? I thought that was the whole point. – tjt263 Mar 10 at 7:02
• @tjt263 No, "doesn't have to be rearranged" is the opposite of "the whole point". Read (the first paragraph of) my answer, and pay attention to the words in bold face. – Andreas Blass Mar 10 at 11:48
• @tjt263 The definition of graph given in many of the answers should be a clue here: a list of vertices and a list of edges. Physical arrangement of vertices doesn't matter for graphs, in general. Related concepts, like planar graphs, may involve vertex placement. – jaxad0127 Mar 10 at 23:40

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.

• That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it. – tjt263 Mar 9 at 19:42
• The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$. – Travis Mar 9 at 19:51
• But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it? – tjt263 Mar 9 at 20:38
• There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph. – Travis Mar 9 at 21:19
• In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 \cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 \cup K_1$ has two. – Travis Mar 9 at 21:21

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.
• So far, I think this answer is making the most sense. When you talk about rotating the image, you must mean in 3D space? But I thought they were 2D only. – tjt263 Mar 10 at 7:30
• I meant in 2D, but the same idea works for 3D too. Our pictures of graphs are in the (2D) plane, and if we turn the 2D plane, say, 90 degrees anticlockwise, we get a perfectly good picture of exactly the same graph (with the labels written vertically!). – Theo Bendit Mar 10 at 8:00
• I don't see it. If you rotate the graph/plane 90°, it just looks like it's been turned on it's side (i.e. ↑ becomes ←). Surely you must be right and I'm wrong, but I'm obviously missing some crucial information here. It's like we're using the same words to describe totally different things. – tjt263 Mar 10 at 8:36
• @tjt263 Yes, the picture has just been turned on its side. Note two things: the picture is different (in that the dots have moved position), but the graph is the same, i.e. the vertices are still $c_1, \ldots, c_n$ and the edges are still the same. I'm trying to demonstrate how the concept of a graph and the picture of the graph are not the same thing. – Theo Bendit Mar 11 at 9:09

# 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, be please careful not to confuse:

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

• @tjt263: Indeed, graph isomorphism doesn't care about coordinates, color, weight or name. The only relevant information is : "are these nodes connected to one another"? – Eric Duminil Mar 10 at 10:17
• @tjt263: The first graph in your question can be perfectly described by "e1-e2-e3-e4-e5-e1". No other information is needed. It might be easier to understand isomorphism once you reduce a graph to its bare minimum. – Eric Duminil Mar 10 at 10:42
• This begs the question. Eg define "continuous movie transforming one graph into the other". (While you're at it--the asker doesn't seem to know what a graph is.) Eg "By dragging around vertices, you cannot create the triangles that are present in the other graph."--Oh? Where is this justified for this movie? How does it imply there's no other movie? (Whatever a movie is.) Etc etc. Re (more) reasons one might downvote: The asker's comment(s). (After inexplicable introductory "This might be the best"--eg the immediate request for an explanation.) PS Please clarify via edits, not comments. – philipxy Mar 10 at 11:00
• @tjt263: I can see I received two upvotes and one downvote. Downvoting isn't a problem per se, it's simply better when there's a comment associated to it. "Bar graph" and "graph" aren't related to each other. A graph can be defined and used without any visualization, a bar chart is a visualization. – Eric Duminil Mar 10 at 11:38
• As @philipxy said, your answer begs the question, and in fact is significantly more complicated than the actual correct definition of isomorphism. You are not only involving continuous deformations, which aren't part of the correct definition, but also not explaining what those things are, nor how to prove based on your wrong definition when there is no isomorphism. – user21820 Mar 10 at 11:45

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.

• People keep saying this, but if you move the vertices, rotate the graph, stretch the edges, etc. it's not the same anymore is it? I mean, how can it be? We've literally just changed it, haven't we? The coordinates are different, or the sequence in which they're connected has changed, so the edges have changed. And so on. If they were the same.. they'd be the same! So they'd look the same. This seems obvious. But it's contrary to the general consensus. I know that you must be right and I must be wrong. But how? Or why? – tjt263 Mar 10 at 9:52
• @tjy263 The thing here is to seperate what a grap is from how we visualize what a graph is. A graph is a pair of a set of vertices and a set of unordered pairs of those vertices (i.e. edges). We can visualize these things in different ways by drawing them out in a descriptive way, but these visualisation s are inherently limited. An anagulous way would be to think of graphs as, say tennis balls connected with rubber strings. We can move and stretch and reorder the balls and strings but the underlying structure (graph) stays the same. – Tande Mar 10 at 10:24
• @tjt263 So the orientation or coordinates or the sequence are not part of the graph, but the representation of the graph. The only thing that matters in a graph is if they have the same amount of vertices connected in the same way (think about the tennis ball analogy). – Tande Mar 10 at 10:49
• Okay, thanks. This is helpful. You said: The thing here is to seperate what a graph is from how we visualize what a graph is. What exactly is a graph then? Is a bar graph not really a graph? What we're doing here seems analogous to say, if we had a bar graph, and we started re-arranging the bars and changing the plotted values, and flipping the axes, then saying the information hasn't changed, when it obviously has. See what I'm getting at? – tjt263 Mar 10 at 10:57
• @tjt263 Yes I can see where the confusion comes from, but no, it has not changed. What has changed is the visual representation of a graph, not the actual graph. When we speak of a graph in mathematical terms all we have is the info of the sets V and E (where the graph G itself is G=(V,E) ) of the vertices and edges respectively. That is all that a graph is in mathematics. Graph is a structure. We can't change the graph without changing the vertices (nodes) or edges. All else is part of other things, like the representation of the graph rather than the graph in itself. – Tande Mar 10 at 12:40

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.

• Excellent answer, with a clear explanation and nice looking diagrams. – Eric Duminil Mar 10 at 10:44
• Eric Duminil, same to you. I just now saw your answer, and those animations are super slick! – AmateurDotCounter Mar 10 at 11:58
• This suffers from the problems I mention in my comments on @EricDuminil's answer. You use a lot of undefined vague terms and you never justify your claims or answer the question. – philipxy Mar 10 at 13:00