Question

An isomorphism of graphs G and H is a bijection f 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 ____________

(a) f(u) and f(v) are contained in G but not contained in H

(b) f(u) and f(v) are adjacent in H

(c) f(u * v) = f(u) + f(v)

(d) f(u) = f(u)^2 + f(v)^2

This question was addressed to me at a job interview.

My enquiry is from Isomorphism in Graphs in section Graphs of Discrete Mathematics

Answer 1

The correct choice is (b) f(u) and f(v) are adjacent in H

To elaborate: 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 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.