written 7.5 years ago by | modified 2.4 years ago by |

**Mumbai University > Computer Engineering > Sem 3 > Discrete Structures**

**Marks:** 8 Marks

**Year:** May 2016

**1 Answer**

0

3.5kviews

Define isomorphic graphs. Show that the following two graphs are isomorphic.

written 7.5 years ago by | modified 2.4 years ago by |

**Mumbai University > Computer Engineering > Sem 3 > Discrete Structures**

**Marks:** 8 Marks

**Year:** May 2016

ADD COMMENT
EDIT

0

241views

written 7.5 years ago by |

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.

ADD COMMENT
EDIT

Please log in to add an answer.