■

http://d.hatena.ne.jp/tikani_nemuru_M/20091104/1257322803

平面上にいくつかの点がある。点と点が線で結ばれている。任意の１点から出ている線の数はＮ。任意の２点を取り出すと、その２点は直接、あるいは、別の１点を経由してつながっている。このような状況が可能な点の個数の最大値は？

N=3は点8個でこうかな…。

N=4では点は13以上だが、14はいけるのだろうか…？

これで気に食わないのは例えばＢ〜ＣにはＡを経る路とｆを経る路の二通りあってどうも非効率的っぽい。
同じくＢ〜ｋもｆとｇを経る路がそれぞれある。
…対称性も考えて無駄が８箇所、ちょっと効率悪いな。あと一点くらいは楽に加えられそうだが…。

追記：http://b.hatena.ne.jp/entry/d.hatena.ne.jp/tikani_nemuru_M/20091104/1257322803
id:takanorikidoさんのブックマークコメントより、番号の振り分けは少し違うけど形としては

あまりにもエレガント…そして理論値。これ以上点は明らかに０からいけない位置にしか押し込めないので無理。いやはや参った…。ということは線が４本のときも何かありそう。

追記２：

やはりN=4で点14いけた。15は無理だろうか…？
この方針で下限4N-2は楽そうだ。ということはN=150で598までは楽。問題はそこからどれだけ上積みできるか。

追記３：
冒頭の引用元にてM=150で軽く5000を越えるとか追記されてて愕然。

追記４：
N=4のとき点15いけた。http://d.hatena.ne.jp/imo758/20091106にて。

追記５：
っていうか点17説が→id:papaopaoさんのhttp://h.hatena.ne.jp/papaopao/9259265355977601854
ん？この点17説、9のノードで13と16がダブってて、14が抜け落ちてるような。
…全部で9-14、9-17、10-13、10-15、11-12、11-16、12-16、13-15、14-17が見つからない。