木エッジのない無向グラフのサイクル？

Question

DFSが実行された無向グラフ（すべてのエッジをツリーエッジまたはバックエッジのいずれかとしてDFSツリーを生成するため）では、バックエッジのみで構成されるグラフのサイクルが存在する可能性があります。木のエッジはありませんか？

Answer 1

たとえば、大きなクリークを取る。クリークから単一のDFSツリーを削除すると、膨大な数のエッジが発生し、結果的に多くのサイクルが発生します。