YOI 839：組めるかどうかは辺の本数では決まらない。近所が自分より小さい一組が在るかどうかだけが決める

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

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi839,
  author = {Yamagishi, Yuuki},
  title = {Whether a Matching Exists Is Not Decided by the Number of Edges, Only by Whether Some Set Has a Smaller Neighbourhood},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/839},
  doi = {10.5281/zenodo.23015624},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

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

書誌

要旨

「手が足りないなら人を増やせばよい」と言いたくなる。本稿は、増やすのが辺でも足りないことを数える。新しい定理も法則も主張しない。

第一に、組めることと、近所の条件は完全に一致する。$65536$ 通りのうち $37823$ 通りで、二つの別々の数え方が食い違わなかった（$0$ 件）（第2節）。

第二に、これが本稿の芯である。辺の本数では分からない。組めるものの最小 $4$ 本と、組めないものの最大 $12$ 本のあいだで、幅 $9$ の帯が重なる（第3節）。

第三に、辺が多くても組めないものが在る。$16$ 本中 $12$ 本も辺がありながら組めないものが $8$ 通りある（第3節）。

第四に、組めないときは必ず証拠が一つ在る。組めない $27713$ 通りすべてで、近所が自分より小さい一組が見つかった（第4節）。

第五に、その証拠はたいてい小さい。大きさ $1$ の一組が最悪だったものが $12500$ 件で、全体の $\mathbf{0.451052}$ を占める（第4節）。

第六に、分離子は、本数を問うか、ある一組の近所を問うかである。本数は足せば増えるが、近所は足しても増えないことがある（第5節）。

キーワード：結婚定理、二部グラフ、完全マッチング、近所、全数え上げ、模型

Abstract

When hands are short, one wants to add more connections.This paper counts that adding edges is not enough.No new theorem or law is claimed.

First, matching and the neighbourhood condition agree completely、across $65536$ graphs, two separate computations both gave $37823$ with no discrepancy (Section 2).

Second, and this is the core. The number of edges tells nothing、between the smallest that matches, $4$, and the largest that does not, $12$, lies an overlapping band of width $9$ (Section 3).

Third, graphs with many edges can still fail、$8$ graphs have $12$ of the $16$ possible edges and admit no matching (Section 3).

Fourth, failure always comes with a witness、in all $27713$ failing graphs a set with a smaller neighbourhood was found (Section 4).

Fifth, the witness is usually small、a set of size $1$ was the worst in $12500$ cases, a share of $\mathbf{0.451052}$ (Section 4).

Sixth, the separator is whether one asks about the count or about one set’s neighbourhood、the count always grows when edges are added; the neighbourhood need not (Section 5).

Keywords: marriage theorem, bipartite graph, perfect matching, neighbourhood, exhaustive enumeration, model

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/839/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/839 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ