誘導パス
次に, Gがk個の独立点集合を持つならば, その独立点集合の頂点をIと入れ替えることで, Hは,必ず長さ2kの誘導パスまたは誘導サイクルを持つことがわかる. 一方, Hが長さkの誘導パスまたは誘導サイクルを持つならば, これらのパスまたはサイクルから得られる隣接していない頂点の極大集合から, Gは,サイズが少なくともk/3の独立点集合を持つことがわかる. よって,Gの最大独立点集合のサイズは,Hの最大誘導パスと最大誘導サイクルのサイズの定数倍以内である. Håstad (1996)による独立点集合の近似不可能性の結果から, NP=ZPPでない限り, 最適解のO(n)以内の最長誘導パスまたは最長誘導サイクルを求める多項式時間アルゴリズムは存在しない.
n個の頂点とm個の辺からなるグラフのホールと,長さ5の誘導サイクルを含まないグラフのアンチホールは, O(n+m)時間で求められる.
多くの重要なグラフクラスは, 誘導パスや誘導サイクルの観点で特徴づけする事ができる.
長さ2の誘導パスを持たない連結グラフは,完全グラフであり,誘導サイクルを持たない連結グラフは,木である.
en:Triange-free graphは,長さ3の誘導サイクルを持たないグラフである.
en:Cographは,長さ3の誘導パスを持たないグラフである.
en:Chordal graphは,長さ4以上の誘導サイクルを持たないグラフである.
en:Even-hole-free graphは,偶数個の頂点からなる誘導サイクルを持たないグラフである.
en:Trivially perfect graphは, 長さ3の誘導パスと長さ4の誘導サイクルのいずれも持たないグラフである.
en:Strong perfect theoremにより, パーフェクトグラフは, 奇数長のホールとアンチホールを持たないグラフであることが知られている.
en:Distance-hereditary graphは,すべての誘導パスが最短路であり,かつ,同じ端点を持つ任意の2つの誘導パスは,その長さが等しくなるようなグラフである.
en:ブロックグラフは,任意の2つの頂点間に高々1つしか誘導パスがないグラフである.また,連結ブロックグラフは,任意の2つの頂点間にちょうど1つ誘導パスがあるグラフである.
無向グラフG中の誘導パスは, Gの誘導グラフかつ道であるグラフのことである. つまり,誘導パスは そのパス上で隣接している任意の頂点対はG中で隣接しており, かつ, 隣接していない任意の頂点対はG中で隣接していないような,G中の頂点の列である. 誘導パスは,スネークとも呼ばれ, 超立方体上の最長誘導パスを発見する問題は, en:Snake-in-the-box問題として知られている.
また, 誘導サイクルは, en:閉路をなすGの誘導グラフのことである. また,誘導サイクルは, コードレスサイクルや,その長さが4以上のとき,ホールとも呼ばれる. アンチホールは, Gの補グラフにおけるホールである.
グラフ中の最長誘導パスの長さは, そのグラフのう回路数と呼ばれる. 任意のen:疎グラフに対して, う回路数が固定された時は,w:tree-depthが固定されている時と等価である. グラフGの誘導パス数とは, グラフを分割するのに必要な最小の誘導パスの数である. また, Gのパス被覆は,Gのすべての頂点を覆うために必要な誘導パスの最小数である. グラフGの内周は, G中の最小のサイクルの長さであるが, そのサイクルは,誘導サイクルである. 同様に,奇内周は, グラフにおける奇数長の最短な誘導サイクルの長さのことである.