スキエナの本より、
エッジ (u,v) と (v,w) をエッジ (u,w) で置き換えることにより、次数 2 の各頂点 v をグラフから削除する線形時間アルゴリズムを設計します。また、エッジの複数のコピーを単一のエッジに置き換えることで排除しようとします。エッジの複数のコピーを削除すると、削除する必要がある次数 2 の新しい頂点が作成される可能性があることに注意してください。また、次数 2 の頂点を削除すると、複数のエッジが作成される可能性があり、これも削除する必要があります。
一般的に、私には少なくともアプローチがあります。この質問については、私は無力です。これは Hw ではなく、私自身の面接準備です。