📂Graph Theory

Graph Isomorphism

Definition ¹

Let two graphs $G_{1}$ and $G_{2}$ be given. If there exists a bijective function between $V(G_{1})$ and $V(G_{2})$, and the number of edges between vertices of $G_{1}$ matches with the corresponding vertices of $G_{2}$, then this bijective function is called an isomorphism, and the two graphs are said to be isomorphic. In other words, a bijective function $\phi : G_{1} \to G_{2}$ satisfying the following is called an isomorphism: $$ u \sim_{1} v \iff \phi (u) \sim_{2} \phi (v) $$

Example

For instance, consider the following two graphs:

Strictly speaking, these two graphs are not the same. Of course, the appearance of a graph is not important when distinguishing them. However, aside from that, they differ because their sets of vertices and edges are distinctly different. However, if a one-to-one correspondence like the following is provided, then the two graphs can essentially be considered the same: $$ A \to x \\ B \to y \\ C \to z \\ D \to u \\ E \to v \\ F \to w $$

See Also

• Isomorphism in Abstract Algebra
• Graph Homeomorphism