Graph isomorphism

Suppose I have two undirected graphs, each with 3 vertices and 3 edges: $G_1$ has $V(G_1)$ = $\{a, b, c\}$ and $E(G_1)$ = $\{(a,b), (a,c), (b,c)\}$, and $G_2$ has $V(G_2)$ = $\{d, e, f\}$, and $E(G_2)$ = $\{(d,e), (d,f), (e,f)\}$. If you draw these graphs, it's pretty clear that they are equivalent: you get $G_2$ by changing the vertex labels $a, b, c$ on $G_1$ to $d, e, f$. But they aren't equal, since their vertex sets and edge sets are different (in a superficial way).

We capture the idea that $G_1$ and $G_2$ are equivalent except for their labeling by saying they are isomorphic. Two graphs $G_1$ and $G_2$ are isomorphic if there is a bijection $f$ such that $f(V(G_1))$ = $V(G_2)$, $f^{-1}(V(G_2)) = V(G_1)$ and $f(E(G_1)) = E(G_2)$. What all the symbols mean is that if you can find a way of matching each vertex of $G_1$ with a corresponding vertex of $G_2$ (this matching is your bijection $f$), and if your matching means that the edges of $G_1$ are mapped to the edges of $G_2$, then $G_1$ and $G_2$ are isomorphic. Another way of saying the same thing is that $v_1$ and $v_2$ are neighbours in $G_1$ if and only if $f(v_1)$ and $f(v_2)$ are neighbours.

We consider graphs up to isomorphism, that is we consider isomorphic graphs to be equivalent, and a property that we prove about one is true of the other. So we talk about the complete graph of order 5, $K_5$. Even though there are many isomorphisms, they are all equivalent.