What criterias do two graphs have to meet in order to be isomorphic?
I know they must have the same number of vertices and edges. Do they both have to be bipartite/non-bipartite?
To determine whether two graphs are isomorphic, they must satisfy both the requirements you mentioned: having the same number of vertices and edges. However, the notion of bipartiteness is not a requirement for graphs to be isomorphic.
Here is a step-by-step approach to check whether two graphs are isomorphic:
1. Count the number of vertices and edges in each graph. If the counts are different, the graphs cannot be isomorphic.
2. Compare the degree sequences of the graphs. The degree of a vertex is the number of edges incident to it. If the degree sequences differ, the graphs are not isomorphic. However, keep in mind that having the same degree sequences is not sufficient to prove isomorphism.
3. Look for any obvious structural differences. Identify unique subgraphs or patterns in one graph that are not present in the other. If any such differences are found, the graphs are not isomorphic.
4. Try to find a mapping between the vertices of the two graphs. In an isomorphism, each vertex of one graph should correspond to a unique vertex in the other graph, and vice versa. This mapping should preserve adjacencies, meaning that if two vertices are connected by an edge in one graph, their corresponding vertices in the other graph should also be connected by an edge. If a valid mapping is found, the graphs are isomorphic.
Remember that this process can be complex and time-consuming for larger graphs. In some cases, it may be helpful to use graph theory software or algorithms specifically designed to determine graph isomorphism.