Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

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

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

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

日付の証拠（OpenTimestamps）

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

書誌

要旨

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

第一に、三つはたいてい等しい。点 $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節）。

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

Abstract

It is easy to assume that a network is robust if every vertex has many edges.This paper counts, over all small graphs, the number of vertices needed to cut, the number of edges needed to cut, and the minimum degree, side by side.No new theorem or law is claimed.

First, the three are usually equal: of the $26704$ labelled connected graphs on $6$ vertices, $25924$ have all three equal, a share of $\mathbf{0.970791}$ (Section 2).

Second, when they differ, minimum degree is the largest: vertex connectivity $\le$ edge connectivity $\le$ minimum degree holds for all, and minimum degree exceeds vertex connectivity in $780$, a share of $\mathbf{0.029209}$ (Section 2).

Third, and this is the core. Every vertex may have three edges, yet removing one vertex can cut the graph: on $8$ vertices, joining two complete graphs on four vertices by two edges from the same vertex gives vertex connectivity $1$, edge connectivity $2$ and minimum degree $3$ (Section 3).

Fourth, on $6$ vertices no graph separates them that far: vertex connectivity $<$ edge connectivity occurs in $690$ and edge connectivity $<$ minimum degree in $90$, but both strict in $0$ (Section 2).

Fifth, cut sizes equal the numbers of paths: recomputing both connectivities as the maximum number of paths sharing no vertex or no edge (maximum flow) agreed with the cut values for $2131$ graphs (Section 2).

Sixth, the separator is whether robustness is measured by minimum degree or by cuts: minimum degree looks only around one vertex; a cut looks for the thinnest place in the whole network. The former is only an upper bound on the latter (Section 4).

Keywords: vertex connectivity, edge connectivity, minimum degree, Whitney’s inequality, Menger’s theorem, cut

版の記録

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

YOI の一覧へ