Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

どの点にも辺がたくさんあれば、網は壊れにくい、と思いやすい。本稿は、点で切る数・辺で切る数・最小次数の三つを、小さいグラフで全部数えて並べる。新しい定理も法則も主張しない。

第一に、三つはたいてい等しい。点 $6$ 個のラベル付き連結グラフ $26704$ 個のうち、三つが等しいのは $25924$ 個、割合 $\mathbf{0.970791}$ である（第2節）。

第二に、等しくないときは、最小次数がいちばん大きい。点連結度 $\le$ 辺連結度 $\le$ 最小次数 はすべてで成り立ち、最小次数が点連結度より大きいのは $780$ 個、割合 $\mathbf{0.029209}$ である（第2節）。

第三に、これが本稿の芯である。どの点にも辺が三本あっても、一点を抜けば切れることがある。点 $8$ 個で四点の完全グラフ二つを同じ点から出した二本の辺で結ぶと、点連結度 $1$・辺連結度 $2$・最小次数 $3$ になる（第3節）。

第四に、点 $6$ 個では、そこまで離れたグラフは一つも無い。点連結度 $<$ 辺連結度 は $690$ 個、辺連結度 $<$ 最小次数 は $90$ 個あるが、二つとも真に小さいものは $0$ 個である（第2節）。

第五に、切り口の数は道の本数と一致する。切り口を全部試して出した連結度を、点や辺を共有しない道の本数（最大流）で出し直すと、$2131$ 個のグラフで一致した（第2節）。

第六に、分離子は、壊れにくさを最小次数で測るか、切り口で測るかである。最小次数は一点のまわりだけを見て、切り口は網全体の細いところを見る。前者は後者の上限でしかない（第4節）。

キーワード：点連結度、辺連結度、最小次数、ホイットニーの不等式、メンガーの定理、切り口。

射程（何を示さないか）

新しい定理も法則も主張しない。点連結度 $\le$ 辺連結度 $\le$ 最小次数（ホイットニーの不等式）と、連結度が点や辺を共有しない道の本数に等しいこと（メンガーの定理）は、いずれも既知である。定理を証明しない。点 $6$ 個のグラフを全部数え、構成した例で確かめるだけである。大きさを一般化しない。点 $7$ 個以上は全部を数えていない。設計を助言しない。実在の通信網や道路網をどう作るべきかは述べない。既刊との関係：論文838 は、流れを絞っているのは細い辺ではなく細い切り口であることを示した。本稿はその隣に置く。あちらは辺の切り口と流れを数えた。ここでは点の切り口・辺の切り口・最小次数の三つを並べ、最小次数が切り口の上限でしかないことを数える。加えたのは、点 $6$ 個の連結グラフ $26704$ 個で三つの組を全部数えたこと、三つが等しい割合 $0.970791$ を測ったこと、点 $8$ 個で $(1,2,3)$ の例を作ったこと、分離子を「最小次数か、切り口か」に置いたことである。

1. 記法と問い

設定：連結なグラフ $G$ について、三つの量を置く。点連結度 $\kappa$ は抜くと残りが繋がらなくなる点の最小の個数、辺連結度 $\lambda$ は抜くと繋がらなくなる辺の最小の本数、最小次数 $\delta$ は点につく辺の本数の最小である。

$$\kappa(G)\le\lambda(G)\le\delta(G),\qquad
\lambda(G)=\min_{\emptyset\ne S\subsetneq V}\bigl|E(S,V\setminus S)\bigr|$$

点 $6$ 個のラベル付きグラフ $32768$ 個をすべて作り、連結なものについて三つを数えた。点連結度は点の部分集合を全部試し、四点の完全グラフのように抜いても切れないものは $n-1$ とした。

問い：どの点にも辺が多ければ、網は切れにくいのか。

2. 点 $6$ 個を全部数える

計算 2.1：連結グラフ $26704$ 個について、三つの組ごとの個数を数えた。

観察 2.2　三つはたいてい等しく、等しくないときは最小次数がいちばん大きい。三つが等しいのは $25924$ 個（$0.970791$）で、点連結度 $\le$ 辺連結度 $\le$ 最小次数 はすべてで成り立った。最小次数が点連結度より大きいのは $780$ 個（$0.029209$）、点連結度 $<$ 辺連結度 は $690$ 個（$0.025839$）、辺連結度 $<$ 最小次数 は $90$ 個（$0.003370$）で、二つとも真に小さいものは $0$ 個だった。

観察 2.3　切り口の数は、道の本数と一致する。切り口を全部試して出した二つの連結度を、点や辺を共有しない道の最大本数（容量 $1$ の最大流）で出し直した。無作為に選んだ $2131$ 個のグラフで、どちらの連結度も一致した。

3. 一点で切れる、辺の多いグラフ

計算 3.1：点 $8$ 個で、四点の完全グラフ二つ（点 $0$〜$3$ と点 $4$〜$7$）を二本の辺で結んだ。

観察 3.2　これが本稿の芯である。どの点にも辺が三本あっても、一点を抜けば切れることがある。同じ点から二本を出すと、その点を抜くだけで二つの塊は離れる。辺で切るには二本が要り、どの点にも辺は三本以上あるので、三つはすべて違う値 $(1,2,3)$ になる。点 $6$ 個では一つも無かった形である。

4. 分離子

観察 4.1　分離子は、壊れにくさを最小次数で測るか、切り口で測るかである。最小次数は一つの点のまわりだけを見る。切り口は網全体でいちばん細いところを見る。一点のまわりが太くても、網のどこかに細い首があれば、そこで切れる。最小次数は切り口の上限でしかない。

観察 4.2　論文838 の隣に置く。838 は、流れを絞っているのが細い辺ではなく細い切り口であることを示した。そこでは辺の切り口が流れを決めた。ここでは同じ切り口を点と辺の二通りで数え、さらに最小次数と並べた。どちらも「局所の太さではなく、全体の切り口」という同じ側に立つ。

観察 4.3　言わないこと。定理の証明も、点 $7$ 個以上の全数え上げも、実在の網の設計も扱わない。示したのは、最小次数が大きくても切り口は小さくありうるということである。

5. 点呼と結び

1. 点連結度 $\le$ 辺連結度 $\le$ 最小次数（第1節）：ホイットニーの不等式。
2. 連結グラフ $26704$ 個（計算 2.1）：点 $6$ 個のすべて。
3. 三つが等しい $\mathbf{0.970791}$（観察 2.2）：たいてい等しい。
4. 最小次数が大きい $\mathbf{0.029209}$（観察 2.2）：$780$ 個。
5. 点連結度 $<$ 辺連結度 $690$ 個（観察 2.2）：点で切るほうが安い。
6. 辺連結度 $<$ 最小次数 $90$ 個（観察 2.2）：辺の切り口が細い。
7. 二つとも真に小さい $0$ 個（観察 2.2）：点 $6$ 個では無い。
8. 点 $8$ 個で $(1,2,3)$（計算 3.1）：本稿の芯。
9. 切り口と道の本数が一致（観察 2.3）：メンガーの定理・$2131$ 個。
10. 最小次数か、切り口か（観察 4.1）：分離子・論文838。

結び：どの点にも辺が三本あっても、一点を抜けば切れることがある。点 $6$ 個の連結グラフ $26704$ 個では、点連結度・辺連結度・最小次数の三つが等しいのが $0.970791$ で、等しくないときは最小次数がいちばん大きかった。最小次数は一点のまわりだけを見るので、網全体の細い首を見落とすからである。点 $8$ 個で四点の完全グラフ二つを同じ点から出した二本の辺で結ぶと三つは $(1,2,3)$ になり、どの点にも辺が三本以上あるのに、その一点を抜けば切れる。点 $6$ 個では、二つとも真に小さいグラフは一つも無かった。既刊との位置：論文838 の「細い辺ではなく細い切り口」の隣に、点の切り口と辺の切り口と最小次数の三つを並べた。正直に言えば、全部を数えたのは点 $6$ 個までで、定理は既知として使い、確かめただけである。

参考文献

1. Bollobás, B. (1998). Modern Graph Theory. Springer.
2. Whitney, H. (1932). Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics.
3. 山岸勇輝 (2026). 『流れを絞っているのは細い辺ではなく、細い切り口である』[論文838]. YOI: https://www.yamagishiyuuki.com/yoi/838 ・ DOI: 10.5281/zenodo.23015618

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

書誌

山岸勇輝（2026）「どの点にも辺が三本あっても、一点を抜けば切れることがある」［論文868］. YOI: https://www.yamagishiyuuki.com/yoi/868

@misc{yamagishi2026yoi868,
  author = {Yamagishi, Yuuki},
  title = {Every Vertex May Have Three Edges, Yet Removing One Vertex Can Cut the Graph},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/868},
  note = {Preprint, edition 1}
}