組合せとグラフの理論(塩田)第2回 (4) 部分グラフ

部分グラフ

 グラフの一部分でグラフになっているものを「部分グラフ」と呼びます。 例えば
$G=$
の部分グラフとして
とか とか
があります。
注意
  • $G$ 自身も $G$ の部分グラフと考えます。
  • 頂点をすべて含む必要はありません。
  • ただし、辺の両端の頂点は必ず入れます。
こういうのはダメ