Isomorphic and homeomorphic graphs

Non- Isomorphic Graph

Non-isomorphism is more accessible to check than isomorphism. Two graphs are non-isomorphic if any of the following conditions are met:

• The number of connected components is different
• Vertex-set cardinalities are different
• Edge-set cardinalities are different
• Degree sequences are different

Example

                                         

                         G                                                                                        G’

How To Determine Whether A Graph Is Isomorphic

G and H are two simple graphs that we are given. If there is a structure that retains a one-to-one connection between the vertices and edges, graphs G and H are isomorphic.

In other words, the only difference between the two graphs is the names of the edges and vertices.

Checklist

Take a look at the graphs below. Is it true that they're both isomorphic?

Is It Possible To Tell If Two Graphs Are Isomorphic?

We need to ask the following questions:

• Are there the same number of vertices in both graphs? Both graphs do have four vertices.
• Are there the same number of edges in both graphs? Both graphs do contain four edges.
• Is the degree sequence the same in both graphs? Each vertex has a degree of two.
• May we discover the same cycle length in the other graph. Can a cycle of length k be formed by the vertices in one graph? Yes, each graph has a four-cycle cycle.
• And the graphs are isomorphic if we can answer yes to all four preceding questions. Put another way; they're the same graphs in different shapes.

 

And the graphs are isomorphic if we can answer yes to all four preceding questions. Put another way; they're the same graphs in different shapes.

Relabeling

Relabeling is a straightforward approach to testing an isomorphism between two simple graphs in addition to counting vertices, edges, degrees, and cycles.

Let's say we wish to show that the two graphs below are isomorphic.

Two Graphs — Isomorphic Examples

First, we double-check the number of vertices and degrees to ensure that both graphs contain five vertices and that the degree sequence is in ascending order (2,2,2,3,3).

We'll start labeling vertices one by one, starting with degree 3 vertices and marking with a and b.

 

Odd Vertices should be labeled.

Next, we note that a vertex is near to both a and b in both graphs. Therefore we call this vertex c in both graphs.

Adjacent Vertex Label

As a result, there are only two vertices left, which we name d and e, where d is next to a and e is adjacent to b.

Vertices that remain to be labeled

Finally, we verify one-to-correspondence by relabeling each graph and defining our isomorphism.

a=f(1)
b=f(2)
c=f(3)
d=f(4)
e=f(5)

 

If graph G has n vertices and graph H has m edges, this isn't the only way to define the isomorphism. The number of vertices from which bijections can be made is n! There are m! bijections from the edges if the vertices form a cycle of length k, (n!)(m!) pairs of functions to check.

There are numerous options available. Because there is no efficient or one-size-fits-all method for determining whether two graphs are isomorphic, the best method is to discover if they are not. Vertices, edges, and degrees should all be checked!

Let us demonstrate that the next pair of graphs is not an isomorphism.

The first step is to count the edges and vertices and compare them. Then we check to see if the degree sequence is also equal. Then, as long as the first several queries have yielded a matched result, we look for the most extended cycle. Finally, we'll use technique 2 to construct our isomorphism by relabeling.

The degree sequence is the best technique for assessing if two graphs are isomorphic in the following two situations.

  

                  G                                                                                       H

Degree Sequence

G: {2, 2, 2, 2, 3, 3}

H: {2, 2, 2, 2, 2, 2}

      G≇H

 

Degree Sequence —Not  Isomorphic

                    G                                                                                   H

Degree Sequence

G: {2, 2, 3, 3, 3, 3}

H: {2, 2, 3, 3, 4, 4}

      G≇H

Degree Sequence — Not Isomorphic

Connectivity

Even though two graphs are not isomorphic, their graph invariants—the number of vertices, edges, and degrees of vertices—are often identical. Paths and circuits can assist in distinguishing between the graphs in this scenario.

 

 

Both graphs have six vertices, nine edges, and the same degree sequence. On the other hand, the second graph has a circuit with a length of 3, whereas the first graph's minimum circuit length is 4. As a result, the graphs presented are not isomorphic.

Homeomorphic Graph

A graph homomorphism F from a graph G = (V, E) to a graph G’ = (V’, E’) is written as:

f : G –> G’. It is a mapping f: V –> V’ from the vertex set of G to the vertex set of G’ such that {u, v} ∈ E ⇒ {f(u), f(v) ∈ E’.

In simple words, If another graph G* can be formed by dividing the edge of G with additional vertices, or if a Graph G* can be obtained by introducing vertices of degree 2 in any edge of a Graph G, then the graph G* is complete. Both the graphs G and G*  are known as Homeomorphic graphs.

Properties of Homeomorphic Graph

• Homomorphism always retains a graph's edges and connectedness.
• If a homomorphism is a bijective mapping, then it is an isomorphism.
• The compositions of homomorphisms are also homomorphisms.
• Finding out if there is any homomorphic graph of another graph is an NP-complete problem.

Example

                            G                                                                           G’

 

                            H                                                                                 H’

 

As we can see in both examples, G' can be derived from G,' and H' can be derived from H by introducing a vertex of degree 2.

Frequently Asked Questions

What are isomorphic graphs?

Isomorphic graphs (denoted by G ≅ G') are two graphs with the same number of vertices and are connected in the same way.

What are homeomorphic graphs?

If both can be derived from the same graph by subdivisions of edges, then the graph is said to be homeomorphic.

What is the degree of the vertices?

The degree of a vertex in a graph is the number of edges incident on that vertex.

Conclusion

This blog has discussed isomorphic and homeomorphic graphs, their properties, and examples. Also demonstrated how we can determine if the given graph is an isomorphic graph or not.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!