Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

三角形を作らないように辺を足していき、もう足せなくなったら、それがいちばん辺の多い形だ、と思いやすい。本稿は、小さいグラフを全部数えて、足せなくなった形と最も多い形が別であることを数える。新しい定理も法則も主張しない。

第一に、最も多い本数には天井がある。点 $3$〜$7$ 個のどれでも、三角形の無いグラフの辺は $\lfloor n^2/4\rfloor$ 本を超えられず、その一本上では $0$ 個だった（第2節）。

第二に、最も多い形は必ず二組に分かれている。ちょうど $\lfloor n^2/4\rfloor$ 本のものはすべて釣り合った完全二部グラフで、個数は点 $6$ 個で $10$、点 $7$ 個で $35$、つまり二組への分け方の数である（第2節）。

第三に、これが本稿の芯である。足せなくなっても、最も多いとは限らない。点 $6$ 個で足せなくなった形 $211$ 個のうち、最も多い $9$ 本に届くのは $10$ 個、割合 $\mathbf{0.047393}$ だけである（第3節）。

第四に、多くは途中の本数で止まる。点 $6$ 個では $180$ 個、割合 $\mathbf{0.853081}$ が $7$ 本で止まり、それらはすべて二部でない。点 $5$ 個では五角形の $5$ 本で止まるものが $12$ 個ある（第3節）。

第五に、二組に分かれていても、釣り合わなければ足りない。点 $6$ 個で足せなくなった完全二部グラフは、組の大きさ $(1,5)$・$(2,4)$・$(3,3)$ に応じて $5$・$8$・$9$ 本で、個数 $6$・$15$・$10$ は分け方の数に一致した（第3節）。

第六に、分離子は、これ以上足せないこと（極大）を問うか、最も多いこと（最大）を問うかである。足していく手順が止まる場所は極大であり、最大は全部を見渡さないと分からない（第4節）。

キーワード：マンテルの定理、トゥランの定理、三角形の無いグラフ、完全二部グラフ、極大と最大。

射程（何を示さないか）

新しい定理も法則も主張しない。三角形の無いグラフの辺が $\lfloor n^2/4\rfloor$ 本を超えないこと（マンテルの定理）、その最大が完全二部グラフで達せられること（トゥランの定理の最初の場合）、極大と最大が違うことは、いずれも既知である。定理を証明しない。点 $3$〜$7$ 個で数えて確かめるだけである。避ける形を広げない。四点の完全グラフなど、三角形より大きい形を避ける場合は数えていない。大きさを一般化しない。足せなくなった形を全部数えたのは点 $6$ 個まで、最大を数えたのは点 $7$ 個までである。既刊との関係：論文839 は、組めるかどうかは辺の本数では決まらず、近所が自分より小さい一組が在るかどうかだけが決めることを示した。本稿はその隣に置く。あちらは二組に分かれたグラフの中で組み合わせを数えた。ここでは三角形を避けて辺を最も多く引くと、グラフのほうが二組に分かれることを数える。加えたのは、点 $3$〜$7$ 個で天井の一本上が $0$ 個だと数えたこと、足せなくなった形 $211$ 個のうち最大に届く割合 $0.047393$ を測ったこと、止まる本数を組の大きさと二部かどうかで分けたこと、分離子を「極大か、最大か」に置いたことである。

1. 記法と問い

設定：番号の付いた点 $n$ 個の上のグラフで、どの三点も三角形をなさないものを考える。辺の本数が最も多いものを最大、どの辺を足しても三角形ができるものを極大と呼ぶ。

$$\max\{|E|:\ G\ \text{に三角形が無い}\}=\Bigl\lfloor \frac{n^2}{4}\Bigr\rfloor,\qquad
\text{最大}\ \Rightarrow\ \text{極大},\quad \text{極大}\ \not\Rightarrow\ \text{最大}$$

点 $3$〜$7$ 個では、$\lfloor n^2/4\rfloor$ 本と、その一本上の辺の選び方を全部試した。点 $5$ 個と $6$ 個では、すべてのグラフについて三角形が無いか、極大かを調べた。

問い：三角形を避けて辺を足していき、もう足せなくなったら、それは最も多い形か。

2. 最も多い本数

計算 2.1：点の数ごとに、$\lfloor n^2/4\rfloor$ 本とその一本上で、三角形の無いグラフを数えた。

観察 2.2　最も多い形は、必ず釣り合った二組に分かれている。$\lfloor n^2/4\rfloor$ 本の三角形の無いグラフは、点 $3$〜$7$ 個のすべてで完全二部グラフだった。個数は二組への釣り合った分け方の数で、点 $6$ 個で $10$、点 $7$ 個で $35$ である。一本足すと、どの選び方でも三角形ができた。

3. 足せなくなった形

計算 3.1：点 $5$ 個と $6$ 個で、極大な三角形の無いグラフを辺の本数と完全二部かどうかで分けた。

観察 3.2　これが本稿の芯である。足せなくなっても、最も多いとは限らない。点 $6$ 個で足せなくなった形は $211$ 個あり、最も多い $9$ 本に届くのは $10$ 個、割合 $0.047393$ だけである。$180$ 個、割合 $0.853081$ は $7$ 本で止まる。点 $5$ 個でも、五角形の $5$ 本で止まるものが $12$ 個、割合 $0.444444$ ある。

観察 3.3　止まる本数は、形で分かれる。足せなくなった二部グラフは必ず完全二部で、組の大きさが釣り合わないほど本数が少ない。点 $6$ 個の $(1,5)$・$(2,4)$・$(3,3)$ は $5$・$8$・$9$ 本で、個数 $6$・$15$・$10$ は分け方の数に一致した。二部でないものは、すべて $7$ 本で止まった。

4. 分離子

観察 4.1　分離子は、これ以上足せないこと（極大）を問うか、最も多いこと（最大）を問うかである。辺を一本ずつ足していく手順が止まる場所は、極大である。それが最大かどうかは、その場からは分からない。点 $6$ 個では、足せなくなった形の $0.047393$ しか最大に届かず、残りは最大の手前で止まっている。

観察 4.2　論文839 の隣に置く。839 は、組めるかどうかが辺の本数では決まらず、近所が自分より小さい一組の有無だけで決まることを示した。そこでは二組に分かれたグラフが前提だった。ここでは三角形を避けて最も多く辺を引くと、グラフのほうが釣り合った二組に分かれることを数えた。

観察 4.3　言わないこと。定理の証明も、三角形より大きい形を避ける場合も、点 $8$ 個以上も扱わない。示したのは、足せなくなった形と最も多い形が別だということである。

5. 点呼と結び

1. 天井は $\lfloor n^2/4\rfloor$ 本（第1節）：マンテルの定理。
2. 一本上は $0$ 個（計算 2.1）：点 $3$〜$7$ 個。
3. 最大はすべて完全二部（観察 2.2）：釣り合った二組。
4. 点 $7$ 個で $35$ 個（計算 2.1）：分け方の数。
5. 足せなくなった形 $211$ 個（計算 3.1）：点 $6$ 個。
6. 最大に届く $\mathbf{0.047393}$（観察 3.2）：本稿の芯。
7. $7$ 本で止まる $\mathbf{0.853081}$（観察 3.2）：二部でない。
8. 五角形で止まる $12$ 個（計算 3.1）：点 $5$ 個。
9. $(1,5)$・$(2,4)$・$(3,3)$ は $5$・$8$・$9$ 本（観察 3.3）：釣り合いが本数を決める。
10. 極大か、最大か（観察 4.1）：分離子・論文839。

結び：三角形を避けて辺を足していき、足せなくなっても、最も多いとは限らない。点 $6$ 個で足せなくなった形 $211$ 個のうち、最も多い $9$ 本に届くのは $10$ 個、割合 $0.047393$ だけで、$180$ 個は $7$ 本で止まる。足していく手順が止まるのは極大であって、最大は全部を見渡さないと分からないからである。最も多い形のほうは、点 $3$〜$7$ 個のすべてで釣り合った完全二部グラフで、その一本上では三角形が必ずできた。二組に分かれていても釣り合わなければ、点 $6$ 個で $5$ 本や $8$ 本で止まる。既刊との位置：論文839 が前提にした二組に分かれたグラフの隣に、三角形を避けて最も多く引くとグラフが二組に分かれることを置いた。正直に言えば、数えたのは点 $7$ 個まで（足せなくなった形は $6$ 個まで）で、定理は既知として使った。

参考文献

1. Bollobás, B. (1998). Modern Graph Theory. Springer.
2. 山岸勇輝 (2026). 『組めるかどうかは辺の本数では決まらない。近所が自分より小さい一組が在るかどうかだけが決める』[論文839]. YOI: https://www.yamagishiyuuki.com/yoi/839 ・ DOI: 10.5281/zenodo.23015624

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「三角形を避けて辺を足していき、足せなくなっても、最も多いとは限らない」［論文871］. YOI: https://www.yamagishiyuuki.com/yoi/871

@misc{yamagishi2026yoi871,
  author = {Yamagishi, Yuuki},
  title = {Adding Edges While Avoiding Triangles Until None Can Be Added Does Not Give the Most Edges},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/871},
  note = {Preprint, edition 1}
}