Graph Isomorphism

Graph Theory · Axiom Academy

Understanding when two graphs have the same structure despite different appearances Two graphs G and H are isomorphic if there exists a bijection (one-to-one correspondence) between their vertices that preserves adjacency. In other words, we can relabel the vertices of one graph to exactly match the structure of the other. Graphs G = (V, E) and H = (W, F) are isomorphic (written G ≅ H) if there exists a bijection f: V → W such that for all vertices u, v in V: The function f is called an isomorphism . It maps vertices to vertices while preserving all edge relationships. If two graphs are isomorphic, they must share certain properties called invariants . These are properties preserved by any isomorphism. If graphs differ in any invariant, they cannot be isomorphic. Number of vertices: |V(G)| = |V(H)| Number of edges: |E(G)| = |E(H)| Degree sequence: The sorted list of all vertex degrees must match Number of connected components: Must be the same Cycle structure: Same number of cycles of each length Chromatic number: Minimum colors needed to color vertices Important: Matching invariants is necessary but not sufficient for isomorphism. Two graphs can have identical invariants but still be non-isomorphic! 3. Proving Graphs ARE Isomorphic To prove two graphs are isomorphic, you must find an explicit bijection between vertices that preserves all edges. This requires matching vertices with the same degree and verifying all adjacencies are preserved.

This is the written version of the interactive lesson above. See the full Graph Theory course.