Clear Definition of Two Graphs Being Isomorphic

Question

I am wanting to deal with canonical graph homorphisms and other graph homorphisms much more deeply, but I need a definition for isomorphism between graphs to start. I know the definition of two groups being isomorphic, but I do not know how to tell if two graphs are isomorphic to each other. I watched a video which explains how to tell if two graphs are isomorphic. Now, the video states the following definition of isomorphic graphs: $G_1\cong G_2$ iff $\exists f : V(G_1)\xrightarrow[]{\text{bijection}} V(G_2)$ ST $f(u)f(v)\in G_2 \leftrightarrow uv\in G_1$. Personally, I find this definition hard to work with for two reasons:

• Reason 1: How can I draw a table similar to that of groups in abstract math?
• Reason 2: How is there even an operation defined in this way? It seems as though the operation is not closed (it also seems to be more of a directed graph than an undirected graph in the way that it is not a set), and it does not resemble that of the abstract algebra definition which would be in this case by the functions codomain the following: $G_1\cong G_2$ iff $\exists f : V(G_1)\xrightarrow[]{\text{bijection}} V(G_2)$ ST $\forall u, v \in V(G_1)$, [$f(u\cdot v)=f(u)\diamond f(v)$].

---

• QUESTION:

Is there a good definition of isomorphism between graphs that I should be using by you graph theory/abstract algebra/other experts? Any help would be greatly appreciated!

Above are two graphs which I represented as a table like that of an adjacency matrix if this helps answer the question by giving an example to talk about. So, $G_1:=(V(G_1), E(G_1))$ (shown on the left) and $G_2:=(V(G_2), E(G_2))$ (shown on the right).

So, in this context, $f=\begin{pmatrix} v_1 & v_2 & v_3 \\ v_4 & v_5 & v_6 \end{pmatrix}$.

\begin{array}{c||c||c||c} Adjacency(G_1) & v_1 & v_2 & v_3 \\ \hline v_1 & 0 & 2 & 0 \\ \hline v_2 & 2 & 0 & 1 \\ \hline v_3 & 0 & 1 & 0 \end{array}

\begin{array}{c||c||c||c} Adjacency(G_2) & v_4 & v_5 & v_6 \\ \hline v_4 & 0 & 2 & 0 \\ \hline v_5 & 2 & 0 & 1 \\ \hline v_6 & 0 & 1 & 0 \end{array}

Answer 1

I think you learned about isomorphism only in the context of groups. There as you know the definition is that it's a bijection that preserves the group operation.

The notion of "isomorphism" is much more general. Roughly speaking, a function is an isomorphism if it "preserves the structure of the mathematical objects you are studying".

For graphs, the structure is the set of vertices and those pairs of vertices that form edges. The definition of isomorphism you quote is the right one for that structure. (You are right that it needs some clarification to make it clear whether the graph is thought of as directed or not.)

When you study graph theory you learn to use it, even though it's not the same as the definition you know for groups - and there is no "operation". Two isomorphic graphs will have the same adjacency matrix up to permutations of the rows/columns, so the adjacency matrix is sometimes a useful tool for studying graph isomorphism.

There might not be any structure at all. Any bijection between two sets is an isomorphism of sets. Two isomorphic sets have the same cardinality.

Answer 2

With graph theory, there are competing definitions that are incompatible with each other, and you have to be careful regarding which definition you are using. You can see a discussion of this here on wikipedia

Definition #1: A graph is an ordered pair $G=(V,E)$ such that $V$ is a set (called the vertex set), and $E$ is a set of 2 element subsets of $V$ (called the edge set). Given $u,v \in V$, if $\{u,v\} \in E$ we denote $uv = \{u,v\}$.

The definition of isomorphism that you gave in your question applies only to graphs defined according to Definition #1.

However, if you want to define graphs which allow for the examples in your question, you need another definition:

Definition #2: A graph is an ordered triple $(V,E,\partial)$ such that $V$ is a set (called the vertex set), $E$ is a set (called the edge set), and $\partial$ is a function from $E$ to the set of two element subsets of $V$.

For Definition #2, the definition of isomorphism using adjacency tables works perfectly well. In your examples one would write $\partial e_1 = \partial e_2 = \{v_1,v_2\}$ and $\partial e_3 = \{v_2,v_3\}$. One way to write the definition abstractly would be like this:

Isomorphism of graphs (using Definition #2): Two graphs $(V_1,E_1,\partial_1)$ and $(V_2,E_2,\partial_2)$ are isomorphic if there exist bijections $f : V_1 \to V_2$ and $g : E_1 \to E_2$ such that for all $e \in E_1$, if $\partial_1(e) = \{u,v\}$ then $\partial_2(g(e))=\{f(u),f(v)\}$.

Pure graph theorists use a lot of different words to represent the different type of graphs, for example the word "multigraph" is sometimes used for Definition #2, as that wikipedia link explains.

People outside of graph theory itself, who are not concerned with distinguishing between all the different types of graphs and simply want to apply graphs to their work --- which includes topologists like myself --- will simply use the word "graph" for this second definition.

And, actually, there is a still more general kind of graph, which graphs theorists might call something like a "multigraph with loops", but which topologists may continue to call simply a "graph", except that topologists begin to use more topological terminology and call this something like a "1-complex" (there are 2-complexes and 3-complexes and other higher dimensional analogues of graphs).

Answer 3

Consider the following definition of group isomorphism: it is a bijection $f:G_1\to G_2$ such that

$$uvw^{-1}=e_{G_1} \iff f(u)f(v)f(w)^{-1}=e_{G_2}\quad \forall u,v,w\in G_1.$$

And now compare graphs:

$$uv\in E(G_1) \iff f(u)f(v)\in E(G_2)\quad \forall u,v\in V(G_1).$$

Not much difference really.