今回は、すべての頂点の次数が3以上のグラフは$K_4$をマイナーとして含むという話を紹介しようと思います。一見簡単そうな主張ですが、厳密に証明するのは意外と大変です。 1. 主張の内容 以下の主張が成り立ちます。 $G=(V, E)$を無向単純グラフ*1とする。…