明確にするために- c-Expander グラフは、A のノードと B のノードの間に少なくとも 1 つの頂点を持つ c 以上のサイズの 2 つの素集合 (A と B) を持つ有向グラフ G(V,E) です。 .
そのグラフに長さ n-2c+1 の単純な有向パスがあることを証明する必要があります。
何か案は？
(私が得たヒント - DFS を実行しているときに、黒いノードの数が白いノードの数と等しい段階があることを証明します。ここで、黒いノードは作業を終了したノードであり、白いノードはまだ作業していないノードです。取り組み始めました）