Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文871 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/871 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月7日 10:50 に公開します）。

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

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

第一に、最も多い本数には天井がある。点 $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節）。

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

Abstract

It is easy to assume that adding edges without forming a triangle, until none can be added, yields the graph with the most edges.This paper counts all small graphs and finds that the stuck shapes and the fullest shapes are different.No new theorem or law is claimed.

First, the most edges have a ceiling: for every $n$ from $3$ to $7$, a triangle-free graph has at most $\lfloor n^2/4\rfloor$ edges, and one edge more gave $0$ graphs (Section 2).

Second, the fullest shapes are always split in two: every triangle-free graph with exactly $\lfloor n^2/4\rfloor$ edges is a balanced complete bipartite graph; there are $10$ on $6$ vertices and $35$ on $7$, the number of ways to split into two parts (Section 2).

Third, and this is the core. Being unable to add an edge does not mean having the most: of the $211$ stuck graphs on $6$ vertices, only $10$ reach the maximum of $9$ edges, a share of $\mathbf{0.047393}$ (Section 3).

Fourth, most stop part way: on $6$ vertices, $180$, a share of $\mathbf{0.853081}$, stop at $7$ edges, and all of them are non-bipartite. On $5$ vertices, $12$ stop at the pentagon’s $5$ edges (Section 3).

Fifth, split in two is not enough without balance: the stuck complete bipartite graphs on $6$ vertices have $5$, $8$ and $9$ edges for parts $(1,5)$, $(2,4)$ and $(3,3)$, and their counts $6$, $15$ and $10$ match the numbers of ways to split (Section 3).

Sixth, the separator is whether one asks that no edge can be added (maximal) or that the edges are most numerous (maximum): a procedure that adds edges stops at a maximal graph; whether it is the maximum cannot be seen without surveying everything (Section 4).

Keywords: Mantel’s theorem, Turán’s theorem, triangle-free graph, complete bipartite graph, maximal versus maximum

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/871/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/871 はいつも最新の版を指します）。

YOI の一覧へ