院試勉強にもそろそろ飽きてきたので、気分転換に数理情報学専攻の専門数学の予想問題を作ってみました。計数工学科内では有名な（？）話題に関する問題ですが、ちょっとマニアックなので、暇な人は解いてみてください。難易度は難しめ（&分量多め）だと思い…

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