1.7. Graph Isomorphism

Now let us define a graph isomorphism. So, if you see these two graphs, pictorially they are drawn in a different way. So, the first graph is a rectangle whereas the other graph does not look like a rectangle graph because you might be saying that there are two edges which are crossing each other. But if you see closely structurally, they are similar graphs. What do I mean by structurally they are similar graphs, so both the graphs have the same number of nodes namely 4, same number of edges namely 4 edges and even though the vertex names are different in the two graphs.

In this chunk, the concept of graph isomorphism is introduced, which refers to a relationship between two graphs that allows us to transform one graph into the other by renaming the vertices. The essential point is that when two graphs are isomorphic, they contain the same number of vertices and edges, with a perfect correspondence between the connections (edges) among the vertices, albeit with potentially different labels for those vertices. Even if the visual appearance of the graphs differs (like one being rectangular and another appearing crossed), their underlying structure is the same.

Think of two different maps of the same city. One map may use street names and the other may use numbers for the streets, but if you can trace the same routes and connections between neighborhoods on both maps, they are essentially representing the same layout of roads. This is akin to graph isomorphism where two graphs may represent the same relationship between entities but are depicted differently.

So, in that sense they are structurally the same graphs but drawn in a different fashion. In the same way this graph G and this graph G are structurally same, so the node 1 of graph G corresponds to the node a of graph G and so on and you can then verify that structurally if I reinterpret graph G, then I can redraw it in the same way as the graph G.

The chunk emphasizes the specific formal definition of isomorphism. Two graphs, G1 and G2, are defined as isomorphic if one can find a one-to-one mapping (bijection) between their vertices such that if there is an edge connecting vertex u to vertex v in G1, there should be an edge connecting the mapped vertices in G2 as well. This bijective correspondence must hold true in both directions, ensuring that the structure remains intact when the names or labels are changed.

Imagine you have two different teams in a sports league with players having different names but the same positions (e.g., forward, defender). Even though they might be known under different names, if each forward in one team has a corresponding forward in the other team that plays the same way, they can be said to be playing isomorphic games. Their game structures align perfectly despite the varied names.

So, imagine that the vertex set of both the graphs is of cardinality n, then a naive algorithm to check whether the two graphs are isomorphic is to try all possible n! bijections between the vertex at V and the vertex at V and for each of those bijections check this implication is true or not.

Here, the naive approach to determine if two graphs are isomorphic is discussed. This involves generating all possible arrangements of vertex mappings between the two graphs and checking each arrangement to see if the corresponding connections (edges) still hold. The total number of these mappings grows factorially with the size of the vertex set, specifically n!, making this approach computationally impractical for large graphs.

Consider trying to match people in a line to another line based solely on their heights. If everyone in both lines has different names but similar heights, you would have to try every possible pairing to see if everyone matches correctly. As the number of people increases, this process gets exceedingly tedious, akin to the factorial growth of potential matches in graph isomorphism.

So, how do we verify whether two graphs are not isomorphic or not and we can verify whether two graphs are not isomorphic or not by checking for graph invariant properties. So, what are graph invariant properties? They are the properties which should be preserved by isomorphic graphs, that means these are the properties which should be there both in graph G as well as in graph G if at all they are isomorphic.

In this chunk, the concept of graph invariant properties is introduced. These properties must remain unchanged for graphs that are isomorphic and can be used to quickly determine if two graphs cannot be isomorphic. Examples of such properties include the number of vertices, the number of edges, and the degree distribution of the vertices. If any invariant property is violated, the two graphs can be concluded to be non-isomorphic.

Think of graph invariant properties like the rules of a game. If two games are claimed to be the same but one allows for a certain advantage that does not appear in the other, then they cannot be the same game. Similarly, if two graphs have fundamentally different invariant properties, they cannot be considered identical in structure even if they appear similar at first glance.

--