This answer is restricted. Please login to view the answer of this question.

Login NowThe necessary conditions for the graph to be isomorphic are

- nunber of vertices must be equal
- number of edges must be equal
- number of degree of vertices must be equal
- Sub-graph consisting same degree must be same.
- Adjacent matrix must be same.

*Example:* In below, We will check whether below graph is isomorphic.

**Point 1:** No. of vertices of G =No. of vertices of H = 8

**Point 2:** No. of edges of G = No. of edges of H = 10

Degree of verticesof G |
Degree of vertices of H |

deg(a) = 2 | deg(s) = 3 |

deg(b) = 3 | deg(t) = 2 |

deg(c) = 2 | deg(u) = 2 |

deg(d) = 3 | deg(v) = 3 |

deg(e) = 2 | deg(w) = 3 |

deg(f) = 3 | deg(x) = 2 |

deg(g) = 2 | deg(y) = 2 |

deg(h) = 3 | deg(z) = 3 |

**Point 3: **Degree of vertices of G = degre of vertices of H as there ae equal no. of verticeshabing degre 2 and 3.

**Point 4:**Subgraph of G is not equal to sub graph of H

So, They are not isomorphic.

**Problem II:**

Given graph is

Let’s find maximum flow from S to D using S-D cut method.

X | \(\bar{X}\) | K(X, \(\bar{X}\)) |

{A} | {B, C, D, E, F} | 5 + 15 = 20 |

{A, B} | {C,D, E,F} | 15 + 5 + 5 = 25 |

{A, C} | {B, D, E, F} | 5 + 5 + 5 = 15 |

{A, B, C} | {D, E, F} | 5 + 5 + 5 + 5 = 20 |

{A, B, D} | {C, E, F} | 15 + 5 + 15 = 35 |

{A,C, E} | {B, D, F} | 5 + 5 + 5 = 15 |

{A, B, C, D} | {E, F} | 5 + 15 = 20 |

{A, C, D, E} | {B, F} | 5 + 15 = 20 |

{A, B, C, E} | {D, F} | 5 + 5 + 5 = 15 |

{A, B, C, D, E} | {F} | 15 + 5 = 20 |

Here,

maximum flow= minimum cut = 15

Finally, **the maximum flow is 15.**

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion