グラフの基礎定義と基本性質 ― グラフ理論の出発点を固める
無向グラフ・有向グラフの形式的定義から出発し，次数，握手の補題，完全グラフ$K_n$，完全二部グラフ$K_{m,n}$，グラフの同型を証明付きで解説する教科書スタイルの記事．
1 グラフとは何か
定義 1 (無向グラフ).
無向グラフ（undirected graph）とは，空でない有限集合 と， の元の非順序対 （）を元とする集合 の組 をいう． の元を頂点（vertex）， の元を辺（edge）という．辺 に対して と は の端点であるといい， と は隣接する（adjacent）という．
定義 2 (有向グラフ).
有向グラフ（directed graph）とは，空でない有限集合 と， の部分集合 （ただしループ を許すか否かは文脈による）の組 をいう． の元 を弧（arc）と呼び， を始点， を終点という．
定義 3 (多重グラフと単純グラフ).
2頂点間に複数の辺を許すグラフを多重グラフ（multigraph）という．自己ループ も多重辺も持たないグラフを単純グラフ（simple graph）という．本シリーズでは特に断らない限り単純無向グラフを扱う．
以下，グラフの頂点集合を，辺集合をと書き，，とおく．
2 次数と握手の補題
定義 4 (次数).
頂点 に対して， に接続する辺の本数を の次数（degree）といい， または と書く．すなわち
の頂点の次数の最小値を ，最大値を と書く．
定理 5 (握手の補題).
任意のグラフ に対して
が成り立つ．
証明.
各辺 は と にそれぞれ ずつ寄与する．よって左辺の和では各辺がちょうど 回数えられる． □
注意 6.
握手の補題（handshaking lemma）の名前は「パーティーで全員の握手回数の総和は偶数」という解釈に由来する．この補題の直接の帰結として，任意のグラフにおいて奇数次の頂点の個数は偶数である．
例 7.
5頂点のグラフで次数列が であるとき， より辺数は である．一方，次数列 は が奇数なので，このようなグラフは存在しない．
3 完全グラフと完全二部グラフ
定義 8 (完全グラフ).
すべての異なる2頂点が辺で結ばれているグラフを完全グラフ（complete graph）といい，頂点数 の完全グラフを と書く． の辺数は であり，各頂点の次数は である．
定義 9 (二部グラフ・完全二部グラフ).
（）と分割でき， のすべての辺が の頂点と の頂点を結ぶとき， を二部グラフ（bipartite graph）という．さらに の各頂点と の各頂点がすべて辺で結ばれているとき完全二部グラフといい，， のとき と書く． の辺数は である．
完全グラフ：
完全二部グラフ：
4 補グラフ
定義 10 (補グラフ).
単純グラフ に対して， を の補グラフ（complement）という．すなわち である．
定理 11.
任意の単純グラフ （ 頂点）に対して が成り立つ．
証明.
と は の分割をなすので明らかである． □
5 グラフの同型
定義 12 (グラフの同型).
2つのグラフ と が同型（isomorphic）であるとは，全単射 が存在して
が成り立つことをいう．このとき と書く．
注意 13.
グラフの同型は同値関係である（反射性・対称性・推移性を満たす）．グラフ理論では同型なグラフを「同じ」とみなすのが通常である．同型でないことを示すには，頂点数・辺数・次数列などの不変量が異なることを確認すればよい．ただし，すべての不変量が一致しても同型とは限らない．グラフ同型判定問題は に属するが， 完全であるかどうかは未解決問題である．
例 14.
5頂点・5辺で次数列が のグラフは （5-閉路）に同型である．これは頂点数と次数列だけで同型類が定まる例である．一方，同じ次数列 でも と （2つの三角形の非連結和）は同型でない．