Tag: Graph Isomorphism Problem

Graph Isomorphism | Isomorphic Graphs | Examples | Problems

Graph Theory

Graph Isomorphism-

 

Graph Isomorphism is a phenomenon of existing the same graph in more than one forms.

Such graphs are called as Isomorphic graphs.

 

Graph Isomorphism Example-

 

 

Here,

  • The same graph exists in multiple forms.
  • Therefore, they are Isomorphic graphs.

 

Graph Isomorphism Conditions-

 

For any two graphs to be isomorphic, following 4 conditions must be satisfied-

 

  • Number of vertices in both the graphs must be same.
  • Number of edges in both the graphs must be same.
  • Degree sequence of both the graphs must be same.
  • If a cycle of length k is formed by the vertices { v1 , v2 , ….. , vk } in one graph, then a cycle of same length k must be formed by the vertices { f(v1) , f(v2) , ….. , f(vk) } in the other graph as well.

 

Degree Sequence

Degree sequence of a graph is defined as a sequence of the degree of all the vertices in ascending order.

 

Important Points-

 

  • The above 4 conditions are just the necessary conditions for any two graphs to be isomorphic.
  • They are not at all sufficient to prove that the two graphs are isomorphic.
  • If all the 4 conditions satisfy, even then it can’t be said that the graphs are surely isomorphic.
  • However, if any condition violates, then it can be said that the graphs are surely not isomorphic.

 

Sufficient Conditions-

 

The following conditions are the sufficient conditions to prove any two graphs isomorphic.

If any one of these conditions satisfy, then it can be said that the graphs are surely isomorphic.

 

  • Two graphs are isomorphic if and only if their complement graphs are isomorphic.
  • Two graphs are isomorphic if their adjacency matrices are same.
  • Two graphs are isomorphic if their corresponding sub-graphs obtained by deleting some vertices of one graph and their corresponding images in the other graph are isomorphic.

 

PRACTICE PROBLEMS BASED ON GRAPH ISOMORPHISM-

 

Problem-01:

 

Are the following two graphs isomorphic?

 

 

Solution-

 

Checking Necessary Conditions-

 

Condition-01:

 

  • Number of vertices in graph G1 = 4
  • Number of vertices in graph G2 = 4

 

Here,

  • Both the graphs G1 and G2 have same number of vertices.
  • So, Condition-01 satisfies.

 

Condition-02:

 

  • Number of edges in graph G1 = 5
  • Number of edges in graph G2 = 6

 

Here,

  • Both the graphs G1 and G2 have different number of edges.
  • So, Condition-02 violates.

 

Since Condition-02 violates, so given graphs can not be isomorphic.

∴ G1 and G2 are not isomorphic graphs.

 

Problem-02:

 

Which of the following graphs are isomorphic?

 

 

Solution-

 

Checking Necessary Conditions-

 

Condition-01:

 

  • Number of vertices in graph G1 = 4
  • Number of vertices in graph G2 = 4
  • Number of vertices in graph G3 = 4

 

Here,

  • All the graphs G1, G2 and G3 have same number of vertices.
  • So, Condition-01 satisfies.

 

Condition-02:

 

  • Number of edges in graph G1 = 5
  • Number of edges in graph G2 = 5
  • Number of edges in graph G3 = 4

 

Here,

  • The graphs G1 and G2 have same number of edges.
  • So, Condition-02 satisfies for the graphs G1 and G2.
  • However, the graphs (G1, G2) and G3 have different number of edges.
  • So, Condition-02 violates for the graphs (G1, G2) and G3.

 

Since Condition-02 violates for the graphs (G1, G2) and G3, so they can not be isomorphic.

∴ G3 is neither isomorphic to G1 nor G2.

 

Since Condition-02 satisfies for the graphs G1 and G2, so they may be isomorphic.

∴ G1 may be isomorphic to G2.

 

Now, let us continue to check for the graphs G1 and G2.

 

Condition-03:

 

  • Degree Sequence of graph G1 = { 2 , 2 , 3 , 3 }
  • Degree Sequence of graph G2 = { 2 , 2 , 3 , 3 }

 

Here,

  • Both the graphs G1 and G2 have same degree sequence.
  • So, Condition-03 satisfies.

 

Condition-04:

 

  • Both the graphs contain two cycles each of length 3 formed by the vertices having degrees { 2 , 3 , 3 }
  • It means both the graphs G1 and G2 have same cycles in them.
  • So, Condition-04 satisfies.

 

Thus,

  • All the 4 necessary conditions are satisfied.
  • So, graphs G1 and G2 may be isomorphic.

 

Now, let us check the sufficient condition.

 

Checking Sufficient Condition-

 

We know that two graphs are surely isomorphic if and only if their complement graphs are isomorphic.

 

So, let us draw the complement graphs of G1 and G2.

The complement graphs of G1 and G2 are-

 

 

Clearly, Complement graphs of G1 and G2 are isomorphic.

∴ Graphs G1 and G2 are isomorphic graphs.

 

Problem-03:

 

Are the following two graphs isomorphic?

 

 

Solution-

 

Checking Necessary Conditions-

 

Condition-01:

 

  • Number of vertices in graph G1 = 8
  • Number of vertices in graph G2 = 8

 

Here,

  • Both the graphs G1 and G2 have same number of vertices.
  • So, Condition-01 satisfies.

 

Condition-02:

 

  • Number of edges in graph G1 = 10
  • Number of edges in graph G2 = 10

 

Here,

  • Both the graphs G1 and G2 have same number of edges.
  • So, Condition-02 satisfies.

 

Condition-03:

 

  • Degree Sequence of graph G1 = { 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 }
  • Degree Sequence of graph G2 = { 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 }

 

Here,

  • Both the graphs G1 and G2 have same degree sequence.
  • So, Condition-03 satisfies.

 

Condition-04:

 

  • In graph G1, degree-3 vertices form a cycle of length 4.
  • In graph G2, degree-3 vertices do not form a 4-cycle as the vertices are not adjacent.

 

Here,

  • Both the graphs G1 and G2 do not contain same cycles in them.
  • So, Condition-04 violates.

 

Since Condition-04 violates, so given graphs can not be isomorphic.

∴ G1 and G2 are not isomorphic graphs.

 

To gain better understanding about Graph Isomorphism,

Watch this Video Lecture

 

Next Article- Complement of Graph

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.