25/02/27 11:16:52.50 EOenYDRm.net
頂点n個の完全グラフを3彩色可のグラフにするため辺をk本切断する操作を考える。
この時kの最小値をnで表せないかな？
対角線だけ残したグラフと周だけ残したグラフの二つは自明だけど…
2:１３２人目の素数さん
25/02/28 09:12:37.30 EHAzzIyG.net
なんか知らんが頑張れ
3:１３２人目の素数さん
25/03/01 10:42:16.92 fb64tq5C.net
やるかー
時間かかるけどプログラムで計算して表に著して観てみるか
頂点4の時は1本切ればいいけどそれ以降が不透明なんよな
式にできれば帰納法で証明できるだろうからとりあえずそこまで頑張ってみるぜ
4:１３２人目の素数さん
25/03/01 11:02:29.53 fb64tq5C.net
ちなみにchatGPT先生曰くk≒n^2/3らしい。
近似になるのがなんでなのかは分からん。
nk平面における分布をまとめるとそれらしくなるのかもしれないけど。
公式が欲しい。
5:１３２人目の素数さん
25/03/01 22:11:01.33 UQYv3ub4.net
4^2/3は1に全然近くないが
6:１３２人目の素数さん
25/03/03 21:19:29.35 4GEovj34.net
nが3の倍数のときn(n-3)/6
それ以外のとき(n-1)(n-2)/6