>>700
簡単なものは既に一掃されていますね。
アプローチの検討がつかないものばかりが残ったみたいです。
グラフ理論ももちろん関係あります。
小学生に説明できる簡単な問題では、
ある比重の球でない物体を水面に浮かべたときに、安定する形は何か。
という問題は比重0.5以外は未解決です。
平面のタイルの最密な敷き詰め方はほとんどの図形でわかっていないし、
ひもの結び方が何種類あるかも不明。