## Definitions and examples

A (finite, simple) graph $G$ is an ordered pair $G=(V(G),E(G))$ of two finite sets, where $E(G)$ is a set of $2$-element subsets of $V(G)$. The vertices of $G$ are the elements of $V(G)$, and the edges of $G$ are the elements of $E(G)$. The order $|G|$ of the graph $G$ is the cardinality of $V(G)$.

For example, we obtain a graph $G=(V(G),E(G))$ by: $V(G)=\{1,2,3\}$, $E(G)=\bigl\{\{1,2\},\{2,3\}\bigr\}$, which we can draw as follows:

If $\{x,y\}\in E(G)$, we say that $x$, $y$ are adjacent, or neighbors, and we denote it by $x\sim y$.

Two graphs $G_1$, $G_2$ are isomorphic if there is a bijection $f\colon V(G_1)\to V(G_2)$ such that $x\sim y$ if and only if $f(x)\sim f(y)$. In this case, we write $G_1\cong G_2$. We usually do not distinguish between isomorphic graphs.

It is not always easy to determine whether two graphs are isomorphic or not. For example, in the next three graphs, there are exactly two which are isomorphic.

## Exercises

1. Determine the two graphs that are isomorphic.
2. Show that, in our setting of finite graphs, it is actually enough to check that $f$ is a bijection of vertex sets such that $x\sim y$ implies $f(x)\sim f(y)$, in order to show that $f$ is a graph isomorphism.
3. Prove that:
• for any graph $G$, $G\cong G$,
• if $f\colon G_1\to G_2$ is an isomorphism, then $f^{-1}\colon G_2\to G_1$ is an isomorphism.
• if $f_1\colon G_1\to G_2$, and $f_2\colon G_2\to G_3$ are isomorphisms, then $f_2\circ f_1$ is an isomorphism.