グラフ(graph)$G$とは、 空でない集合$V(G)$と、$V(G)$の元の非順序対の族$E(G)$の対
\[ (V(G),E(G)) \]であると定義する。 $V(G)$の各元を頂点(vertex)といい、 $V(G)$を$G$の頂点集合(vertex set)と呼ぶ。 また$E(G)$の各元を辺(edge)といい、 $E(G)$を$G$の辺集合(edge set)と呼ぶ。
$G$の頂点$v,w$に対して、$vw$ が$G$の辺であるとき、 辺$vw$は$v$と$w$を結ぶという。 そのとき、頂点$v$と頂点$w$は隣接(adjacent)しているといい、 頂点$v$と辺$vw$、または頂点$w$と辺$vw$は接続(incident)しているという。 また辺$e$に対して、$V(G)$を頂点集合、$E(G)\setminus\{e\}$を辺集合とするグラフを、 $G$から辺$e$を除去したグラフと呼び、$G\setminus e$と書く。 さらに、$G$の辺の集合$C$に対して、 $G$から$C$に属する辺をすべて除去して得られるグラフを、$G\setminus C$と書く。
同じ頂点どうしを結ぶ辺を、ループ(loop)と呼ぶ。 頂点の対に対して、それらを結ぶ辺が2本以上存在するとき、 そのような辺の集合を、多重辺(multiple edges)と呼ぶ。 ループや多重辺を含まないグラフを、単純グラフ(simple graph)と呼ぶ。
2つのグラフ
\[G=(V,E),\;G'=(V',E')\]に対して、 $V$から$V'$の上への全単射$f$と$E$から$E'$の上への全単射$g$で
\[
\begin{array}{l}
uv\in E\iff f(u)f(v)\in E' \textrel{かつ} \\
g(uv)=f(u)f(v)\ \forall u,v\in V \\
\end{array}
\]
をみたすものが存在するとき、$G$と$G'$は同型(isomorphic)であるという。