誘導部分グラフ

正式には、任意のグラフ G = (V, E) と頂点の任意の部分集合 S ⊂ V に対して、誘導部分グラフ G[S] は頂点集合が S であり、辺集合が E の辺で両端点が S に含まれるものすべてとされる^[1]。この定義は無向グラフと有向グラフだけでなく、同じ頂点対に複数の辺が存在するものを認めた多重グラフ（英語版）に対しても同様である。

誘導部分グラフ G[S] はグラフ G をもとにした S による誘導部分グラフや、（G が曖昧ではない場合は）単に S による誘導部分グラフなどとも呼ばれる。

誘導部分グラフの重要な例を紹介する。

• 誘導パスは、道である誘導部分グラフのことである。辺に重みがついていない場合にはグラフの任意の2頂点間の最短経路は誘導パスである。なぜなら、その経路に新たに辺を追加した場合、その辺が誘導パスを誘導パスでなくす場合には、経路が最短ではなくなるからである。逆に、距離遺伝グラフでは、全ての誘導パスは最短経路になる^[2]。
• 誘導サイクルは、閉路（サイクル）をなす誘導部分グラフのことである。グラフの内周は「最短閉路の長さ」と定義され、その閉路は常に誘導サイクルである。強いパーフェクトグラフ定理によれば、誘導サイクルとその補グラフはパーフェクトグラフの特徴付けにおいて重要な役割を担う^[3]。
• クリークと独立集合は、それぞれ完全グラフまたは空グラフの誘導部分グラフに対応する。
• 頂点の近傍とは、その頂点と、その頂点と辺で直接繋がっている全ての頂点の誘導部分グラフである。