Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2016

A graph can exist in different forms having the same number of vertices, edges, and also the same edge connectivity. Such graphs are called isomorphic graphs. Two graphs G1 and G2 are said to be isomorphic if −

• Their number of components (vertices and edges) is same.
• Their edge connectivity is retained.

Proof:

We see that both the graphs (a) and (b) have equal number of vertices and edges. The vertex corresponds are given below:

The vertex corresponds are given below:

$u_1 \leftrightarrow v_1, u_2 \leftrightarrow v_3, u_3 \leftrightarrow v_5, u_4 \leftrightarrow v_2, u_5 \leftrightarrow v_4, u_6 \leftrightarrow v_6 \ \ or \ \ u_5 \leftrightarrow v_6, u_6 \leftrightarrow v_4.$

Hence, the two graphs are isometric.