Two graphs G and H are said to be isomorphic to each other if there exist a one to one correspondence, say f between the vertex sets V(G) and V(H) and a  one to one correspondence g between the edge sets E(G) and E(H)  with the following conditions.

(i) for every every vertex u in G, there exists a vertex u' in H such that u'=f(u) and vice versa.

(ii) for every edge uv in G, g(uv)=f(u)f(v)=u'v' is H.

Please see some examples.

An isomorphism of graphs G and H is a bijection ƒ between the vertex sets of G and H

such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H.

Two graphs G and H are said to be isomorphic to each other if there exist a one to one correspondence, say f between the vertex sets V(G) and V(H) and a  one to one correspondence g between the edge sets E(G) and E(H)  with the following conditions.

(i) for every every vertex u in G, there exists a vertex u' in H such that u'=f(u) and vice versa.

(ii) for every edge uv in G, g(uv)=f(u)f(v)=u'v' is H.

Please see some examples.

In connection with graph isomorphism you have the 'Graph Isomorphism Problem' (a famous complexity problem in Computer Science) which is the problem of finding out if it is possible to efficiently calculate a descriptor for any graph such that it is unique and complete (completely describes the graph, like a complete invariant). By efficient we mean possible to calculate in polynomial time, which means that the the number of operations in the algorithm to obtain the descriptor for any graph must have a polynomial form on the number of nodes (n). Something like n^k with k constant. 

If such descriptor existed for all graphs you could just compare any two graphs through their descriptor to check if they were the same or not and test the "graph isomorphism" between them this way. For most practical situations this is achievable (the state of the art package might remain "Nauty" from Brendan Mackay that computes a cannonical labelling of the graph as a unique descriptor). However, there are some special cases that resist any approach. In general the Graph Isomorphism Problem is therefore still an open (mostly theoretical) problem.

The difficulty of testing graph isomorphism is related to the challenge of “capturing” graph structure, which has some decades of history [1]. The difficulty of 'efficiently' identifying the “structure” or the “parts” of a graph in order to be able to compare it with other ones (compute the descriptor) has even led this problem to be entitled as a “disease” [2].

[1] Fortin, S. (1996) The Graph Isomorphism Problem. Technical report, University of Alberta.

[2] Read, R., Corneil, D. (1977) The graph isomorphism disease. Journal of Graph Theory, 1, pp. 339-363.

Good luck.

Definition. Let G = {V,E} and G' = {V ',E'} be graphs. G and G' are said to be  isomorphic if there exist a pair of functions f :V →V ' and g : E → E' such that f associates each element in V with exactly one element in V ' and vice versa; g associates each element in E with exactly one element in E' and vice versa, and for each v ∈V , and each e∈ E , if v is an endpoint of the edge e, then f (v) is an endpoint of the edge g(e).

Notes:

* To prove two graphs are isomorphic you must give a formula (picture) for the functions f and g.

* If two graphs are isomorphic, they must have:

- the same number of vertices

- the same number of edges

- the same degrees for corresponding vertices

- the same number of connected components

- the same number of loops

- the same number of parallel edges.

* Further,

- both graphs are connected or both graphs are not

connected, and

- pairs of connected vertices must have the

corresponding pair of vertices connected.

* In general, it is easier to prove two graphs are not

isomorphic by proving that one of the above properties

fails.

Please see the attachment in the following:

http://www.uow.edu.au/~bmaloney/wuct121/GraphsWeek10Lecture2.pdf

Let G1 and G2 be two graphs and let f be a function from the vertex set of G1 to the vertex set of G2. Suppose that

1. f is one-to-one and onto

2. f(v) is adjacent to f(w) in G2 if and only if v is adjacent to w in G1 .

Then we say that the function f is an isomorphism and that the two graphs G1 and G2 are isomorphic. Two graphs G1 and G2 are therefore isomorphic if there is a one-to-one correspondence between vertices of G1 and those of G2 with the property that two vertices of G1 are adjacent if and only if their images in G2 are adjacent.

In practice, it is not a simple task to prove that two graphs are isomorphic. It is much simpler to show that two graphs are not isomorphic by showing an invariant property that one has and other does not. An invariant is a property such that if a graph has it all isomorphic graphs have it. Some of such properties are the number of vertices, the number of edges, degree of a vertex and some others. Note, a complete set of such invariant is unknown.

Two graphs are isomorphic iff for some ordering of their vertices their adjacency matrices are equal.