Graph isomorphism in Discrete Mathematics
The isomorphism graph can be described as a graph in which a single graph can have more than one form. That means two different graphs can have the same number of edges, vertices, and same edges connectivity. These types of graphs are known as isomorphism graphs. The example of an isomorphism graph is described as follows:
The above graph contains the following things:
- The same graph is represented in more than one form.
- Hence, we can say that these graphs are isomorphism graphs.
Conditions for graph isomorphism
Any two graphs will be known as isomorphism if they satisfy the following four conditions:
- There will be an equal number of vertices in the given graphs.
- There will be an equal number of edges in the given graphs.
- There will be an equal amount of degree sequence in the given graphs.
- If the first graph is forming a cycle of length k with the help of vertices {v1, v2, v3, …. vk}, then another graph must also form the same cycle of the same length k with the help of vertices {v1, v2, v3, …. vk}.
Note: The Degree sequence of a graph can be described as a sequence of degree of all the vertices in ascending order.
Important Points
- For any two graphs to be an isomorphism, the necessary conditions are the above-defined four conditions.
- It is not necessary that the above-defined conditions will be sufficient to show that the given graphs are isomorphic.
- If two graphs satisfy the above-defined four conditions, even then, it is not necessary that the graphs will surely isomorphism.
- If the graph fails to satisfy any conditions, then we can say that the graphs are surely not an isomorphism.
Sufficient Conditions for Graph isomorphism
If we want to prove that any two graphs are isomorphism, there are some sufficient conditions which we will provide us guarantee that the two graphs are surely isomorphism. When the two graphs are successfully cleared all the above four conditions, only then we will check those graphs to sufficient conditions, which are described as follows:
- If the complement graphs of both the graphs are isomorphism, then these graphs will surely be an isomorphism.
- If the adjacent matrices of both the graphs are the same, then these graphs will be an isomorphism.
- If the corresponding graphs of two graphs are obtained with the help of deleting some vertices of one graph, and their corresponding images in other images are isomorphism, only then these graphs will not be an isomorphism.
When two graphs satisfy any of the above conditions, then we can say that those graphs are surely isomorphism.
Examples of Graph Isomorphism
There are a lot of examples of graph isomorphism, which are described as follows:
Example 1:
In this example, we have shown whether the following graphs are isomorphism.
Solution: For this, we will check all the four conditions of graph isomorphism, which are described as follows:
Condition 1:
- In graph 1, there is a total 4 number of vertices, i.e., G1 = 4.
- In graph 2, there is a total 4 number of vertices, i.e., G2 = 4.
Here,
There are an equal number of vertices in both graphs G1 and G2. So these graphs satisfy condition 1. Now we will check the second condition.
Condition 2:
- In graph 1, there is a total 5 number of edges, i.e., G1 = 5.
- In graph 2, there is a total 6 number of edges, i.e., G2 = 6.
Here,
There does not have an equal number of edges in both graphs G1 and G2. So these graphs do not satisfy condition 2. Now we cannot check all the remaining conditions.
Since, these graphs violate condition 2. So these graphs are not an isomorphism.
∴ Graph G1 and graph G2 are not isomorphism graphs.
Example 2:
In this example, we have shown whether the following graphs are isomorphism.
Solution: For this, we will check all the four conditions of graph isomorphism, which are described as follows:
Condition 1:
- In graph 1, there is a total 4 number of vertices, i.e., G1 = 4.
- In graph 2, there is a total 4 number of vertices, i.e., G2 = 4.
- In graph 3, there is a total 4 number of vertices, i.e., G3 = 4.
Here,
There are an equal number of vertices in all graphs G1, G2 and G3. So these graphs satisfy condition 1. Now we will check the second condition.
Condition 2:
- In graph 1, there is a total 5 number of edges, i.e., G1 = 5.
- In graph 2, there is a total 5 number of edges, i.e., G2 = 5.
- In graph 3, there is a total 4 number of edges, i.e., G2 = 4.
Here,
- There are an equal number of edges in both graphs G1 and G2. So these graphs satisfy condition 2.
- But there does not have an equal number of edges in the graphs (G1, G2) and G3. So the graphs (G1, G2) and G3 do not satisfy condition 2.
Since, the graphs (G1, G2) and G3 violate condition 2. So we can say that these graphs are not an isomorphism.
∴ Graph G3 is neither isomorphism with graph G1 nor with graph G2.
Since the graphs, G1 and G2 satisfy condition 2. So we can say that these graphs may be an isomorphism.
∴ Graphs G1 and G2 may be an isomorphism.
Now we will check the third condition for graphs G1 and G2.
Condition 3:
- In the graph 1, the degree of sequence s is {2, 2, 3, 3}, i.e., G1 = {2, 2, 3, 3}.
- In the graph 2, the degree of sequence s is {2, 2, 3, 3}, i.e., G2 = {2, 2, 3, 3}.
Here
There are an equal number of degree sequences in both graphs G1 and G2. So these graphs satisfy condition 3. Now we will check the fourth condition.
Condition 4:
Graph G1 forms a cycle of length 3 with the help of vertices {2, 3, 3}.
Graph G2 also forms a cycle of length 3 with the help of vertices {2, 3, 3}.
Here,
It shows that both the graphs contain the same cycle because both graphs G1 and G2 are forming a cycle of length 3 with the help of vertices {2, 3, 3}. So these graphs satisfy condition 4.
Thus,
- The graphs G1 and G2 satisfy all the above four necessary conditions.
- So G1 and G2 may be an isomorphism.
Now we will check sufficient conditions to show that the graphs G1 and G2 are an isomorphism.
Checking Sufficient Conditions
As we have learned that if the complement graphs of both the graphs are isomorphism, the two graphs will surely be an isomorphism.
So we will draw the complement graphs of G1 and G2, which are described as follows:
In the above complement graphs of G1 and G2, we can see that both the graphs are isomorphism.
∴ Graphs G1 and G2 are isomorphism.
Example 3:
In this example, we have shown whether the following graphs are isomorphism.
Solution: For this, we will check all the four conditions of graph isomorphism, which are described as follows:
Condition 1:
- In graph 1, there are total 8 number of vertices, i.e., G1 = 8.
- In graph 2, there are total 8 number of vertices, i.e., G2 = 8.
Here,
There are an equal number of vertices in both graphs G1 and G2. So these graphs satisfy condition 1. Now we will check the second condition.
Condition 2:
- In graph 1, there are total number of edges is 10, i.e., G1 = 10.
- In graph 2, there are total number of edges is 10, i.e., G2 = 10.
Here,
There are an equal number of edges in both graphs G1 and G2. So these graphs satisfy condition 2. Now we will check the third condition.
Condition 3:
- In the graph 1, the degree of sequence s is {2, 2, 2, 2, 3, 3, 3, 3}, i.e., G1 = {2, 2, 2, 2, 3, 3, 3, 3}.
- In the graph 2, the degree of sequence s is {2, 2, 2, 2, 3, 3, 3, 3}, i.e., G2 = {2, 2, 2, 2, 3, 3, 3, 3}.
Here
There are an equal number of degree sequences in both graphs G1 and G2. So these graphs satisfy condition 3. Now we will check the fourth condition.
Condition 4:
- Graph G1 forms a cycle of length 4 with the help of degree 3 vertices.
- Graph G2 is not forming a cycle of length 4 with the help of vertices because vertices are not adjacent.
Here,
Both the graphs G1 and G2 do not form the same cycle with the same length. So these graphs violate condition 4.
Since, Graphs G1 and G2 violate condition 4. So because of the violation of condition 4, these graphs will not be an isomorphism.
∴ Graphs G1 and G2 are not an isomorphism.