グラフ(graph)$G$とは、 空でない集合$V(G)$と$V(G)$の元の非順序対の族$E(G)$の対$\left( V(G) , E(G) \right)$ であると定義する。 ここで、$V(G)$の各元を頂点(vertex)といい、 $V(G)$を$G$の頂点集合(vertex set)と呼ぶ。 また、$E(G)$の各元を辺(edge)といい、 $E(G)$を$G$の辺集合(edge set)と定義する。
$G$の頂点$v, w$に対して、$vw$が$G$の辺であるとき、辺$vw$は$v$と$w$を結ぶという。 同じ頂点どうしを結ぶ辺を、ループ(loop)と呼ぶ。 頂点の対に対して、それらを結ぶ辺が2本以上存在するとき、 そのような辺の集合を、多重辺(multiple edges)と呼ぶ。 ループや多重辺を含まないグラフを、単純グラフ(simple graph)と呼ぶ。
\[ uv \in E \iff f(u)f(v) \in E' \textrel{かつ} g(uv) = f(u)f(v) \forall u,v \in V \]
をみたすものが存在するとき、$G$と$G'$は同型であるという。