8
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ As far as I know, two graphs are equal iff they are isomorphic... $\endgroup$
    – 5xum
    Sep 25, 2014 at 7:36
  • 1
    $\begingroup$ So, do you mean isomorphism and equality are the same thing ? $\endgroup$ Sep 25, 2014 at 7:38
  • 1
    $\begingroup$ As far as I know, yes. $\endgroup$
    – 5xum
    Sep 25, 2014 at 7:40
  • $\begingroup$ What do you mean by that. $\endgroup$ Sep 25, 2014 at 7:51

5 Answers 5

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ If that is the case, can we exploit the difference b/w the equality and isomorphism. I mean is there any application/theorem/result in which only equal graphs are needed not isomorphic graphs ? $\endgroup$ Sep 25, 2014 at 7:46
  • $\begingroup$ @ps06756: there are no "deep" differences but a formally important difference. $\endgroup$
    – Lehs
    Sep 25, 2014 at 7:49
2
$\begingroup$

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
$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I am still having confusion. If two graphs have same diagrams but different names of vertices. So, they are by definition isomorphic, but shouldn't they be equal as well because they have the same diagram and depict the same relationship $\endgroup$ Sep 25, 2014 at 7:43
  • $\begingroup$ @ps06756: In an abstract way they are "equal" but it is important to distinguish between identical (=) and virtually identical. Math is totally depending on a formally correct '='. $\endgroup$
    – Lehs
    Sep 25, 2014 at 7:47
  • $\begingroup$ So, is there any application which distinguishes b/w equality and isomorphic graphs. I mean any result/theorem/application where only equal graphs will work but not isomorphic graphs. $\endgroup$ Sep 25, 2014 at 7:48
  • 1
    $\begingroup$ @ps06756: Graphs are called $C_n,C_{n,m}$ etc, which denote equivalence classes of isomorphic graphs. When you think about a graph, you seems to think about the abstract pattern that is common to all isomorphic graphs. Mathematicians do the same, but must distinguish between them formally, else 1 become 2. $\endgroup$
    – Lehs
    Sep 25, 2014 at 7:56
  • 1
    $\begingroup$ Ok, thanks a lot $\endgroup$ Sep 25, 2014 at 7:57
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.