Isomorphism

Describes when two graphs have the same structure.

Definition 1

The graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic iff there exists a bijection $f: V_1 \to V_2$ such that for any $u,v \in V_1$:

$f$ is called an isomorphism.

Definition 2

The graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic iff there exists a continuous bijection $f: (V_1,E_1) \to (V_2,E_2)$.

Denoted by $G_1 \cong G_2$. $f$ is called an isomorphism.

Isomorphic graphs are denoted by $G_1 \cong G_2$. Has equal number of vertices and edges, and same degree sequence.

Equivalence Relation

Isomorphism is an equivalence relation. Hence, it satisfies:

• Reflexive
  Every graph is isomorphic to itself.
• Symmetric
  If $G_1 \cong G_2$ then $G_2 \cong G_1$.
• Transitive
  If $G_1 \cong G_2$ and $G_2 \cong G_3$ then $G_1 \cong G_3$.

Properties

Isomorphic graphs have the same number of vertices and edges, and the same degree sequence.

They may differ in other properties such as connectivity, planarity, etc.

For bipartite graphs, $K_{a,b}$ and $K_{c,d}$ are isomorphic iff: