ラベル付き木から prüfer sequence（プリューファ列）と呼ばれる整数列への一対一対応を説明します．

グラフ理論の有名な未解決問題である再構成予想について紹介します．

頂点被覆問題がNP完全であることを示します．頂点被覆問題のNP完全性から独立集合問題とクリーク問題がNP完全であることが導かれます．

問題. DAGの最小道被覆問題 DAG が与えられる． の最小道被覆を求めよ．

比較可能グラフが理想グラフであることを示します．

グラフを描画するためのツールをまとめておきます．他に知っている方は教えてくださると喜びます．