Isomorphism vs equality of graphs

Question

I have just started studying graph theory and having trouble with understanding the difference b/w isomorphism and equality of two graphs.According what I have studied so far, I am able to conclude that isomorphic graphs can have same diagrams when represented on paper, but equal graphs also have same diagram on paper, if that is so, then what is the difference b/w equality and isomorphism.

It would be really helpful, if a person could throw some light on what are the difference b/w the above two terms. Specifically, any example of an isomorphic graph which is not equal.

Answer 1

By definition a graph is a set of edges $E\subseteq V^2$ and vertices. An other graph $\bar E\subseteq \bar V^2$ is equal if $E=\bar E$ and $V=\bar V$, but isomorphic if there exists a bijection $f:V\rightarrow \bar V$ such that $(x,y)\in E \Rightarrow (f(x),f(y))\in \bar E$.

Isomorphic is as close as can be when the graphs not have identical sets of edges and vertices.

Answer 2

A graph is a set of vertices and edges. Isomorphic graphs look the same but aren't. For example, the persons in a household can be turned into a graph by decalring that there is an edge $ab$ whenever $a$ is parent or child of $b$. So the graph of the inhabitants of a certin house in Evergreen terrace, Springfield, consists of five vertices where each of "Marge" and "Homer" is directly connected with each of "Bart", "Lisa", "Maggie". We would obtain an isomorphic graph with any other typical couple-with-three-kids household, but not the same (i.e. not all these graphs will contain a vertex named Homer).

Answer 3

In part adding to the answer that Lehs gave. This diagram from Wikipedia demonstrates isomorphism, the labels (vertex set) are changed while the edge set (connectivity?) of the graph stays the same.

I'm not sure if for unlabled graphs isomorphism really is the same as equality.

Answer 4

This two graphs are isomorphic, but not equal. In applications where the graphs are LABELLED, the useful concept might be equality and a mere isomorphism may not be enough.

Mom     Dad

  \    /

   Son

Son     Dad

  \    /

   Mom

Answer 5

Isomorphism preserves vertex adjacency. So that would make the top answer wrong. The two graph examples given are not isomorphic.

Isomorphism is the stringier constraint, since it requires a bijection between the vertices and edges from one graph to another such that vertex adjancencies are preserved.

Equality, on the other hand, only requires that two graphs have the same number of vertices and edges.

For further clarity, you can find the formal definitions here.

Answer 6

I am comming back to this old question for a reason and I would like to add some thoughts which might be helpful for this discussion.

This answer is inspired by a comment in response to this question.

Let me eleborate some context first.

All considered graphs are finite, simple and undirected.

Def. 1: Let $G=(V,E)$ and $G'=(V',E')$ be two graphs. We call $G$ and $G'$ isomorphic, and write $G \simeq G'$, if there exists a bijection $\varphi: V \to V'$ with $(x,y) \in E \iff (\varphi(x), \varphi(y)) \in E', \forall x,y \in V$. Such a map $\varphi$ is called an isomorphism from $G$ to $G'$.

Let us call a graph which has a fully labelled vertex set, a concrete graph.

Now, in most graph theoretic paper, something like the following is stated all the time and it seems very clear at first.

Given two graphs $G$ and $G'$.

A graph $G$ has property $x$ iff $G$ is isomorphic to $G'$.

What we mean is that $G'$ is an abstract representative of some graph for which we ignore concrete (vertex) labeling. $G$ on the other hand can be considered as fully labelled. In that sense: we plug in a concrete graph $G$ and prove isomorphism to $G'$ by creating a concrete labeling for $G'$ a posteriori and we can do that in general for any concrete graph $G$ having property $x$. Usually in the proof the labelling of $G'$ becomes equal to the one in $G$ (because if not, we must define and use the isomorphism map all the time, which is usually omitted). This is in fact found very often. Assume $G'$ is isomorphic to a cycle. You see statements like "Let $G$ be such a graph having property $x$ [... show some stuff ...] then $v_1, \cdots, v_n$ form a cycle, which concludes the proof". But what we mean is: $v_1,\cdots,v_n$ induce a graph isomorphic to a cycle. But what cycle? What isomorphism? The obvious answer is that $v_1,\cdots,v_n$ form the cycle itself.

We might ask "what is graph equality in the first place"? Consider a graph $G=(V,E)$ and $G'=(V',E')$ and assume that $G \simeq G'$ with given isomorphism map $\varphi: V \to V'$, then we can say that $G$ and $G'$ are equal if and only if $V=V'$. The isomorphism map $\varphi:V \to V'$ becomes $\varphi: V \to V$ and is obviously the identity mapping. We can write $G=G'$. In that sense graph equality is just some special isomorphism.

But in fact this scheme is found very inconsistently and often language is abused. Let us say again that $G'$ is a cycle (or should I say "is isomorphic to a cycle"?). Then, it will not take a long time to find a similar statement:

A graph $G$ has property $x$ iff $G$ is a cycle.

What the author really means is: iff $G$ is isomorphic to a cycle. This kind of abuse of language is found very often and is wideley accepted. However, we never say the following (and now for obvious reasons)

A graph $G$ has property $x$ iff $G$ is equal to a cycle.

Let me provide another example which could make the reasoning clear. Given a graph $H$. We call a graph $G$ $H$-free if no induced subgraph of $G$ is isomorphic to $H$. Again, I consider $H$ to be some kind of abstract and in that sense unlabelled graph. We write isomorphic in this setting to underline the fact that we could "plug in" any concrete graph $G$ and define "$H$-freeness". But why is it different than writing: $G$ is $H$-free if no induced subgraph of $G$ is equal to $H$? Because this would be drastically false. Each induced subgraph $X$ of $G$ could only be equal to $H$ if $X \simeq H$ and $V(H)=V(X)$. In that sense we fixed the vertex set of $H$ to be equal to $V(X)$. But each induced subgraph of $G$ differs in at least one vertex, hence $V(H) \neq V(X')$ for an induced subgraph $X'$ of $G$ with $V(X) \neq V(X')$. We can not define $H$-freeness without the notion of isomorphism.