MathLabs

未解決問題、組合せ論と離散数学、1941年に提起

グラフ再構成予想

未解決

GG と HH を n≥3n \ge 3 頂点の有限単純無向グラフとする。それらのデッキ（1頂点を削除して得られるラベルなし誘導部分グラフの多重集合）{G−v:v∈V(G)}\{G - v : v \in V(G)\} と {H−w:w∈V(H)}\{H - w : w \in V(H)\} がカードごとに同型対応するならば、GG と HH は同型である。

研究の最前線 2026年時点

2026年現在、グラフ再構成予想は一般の有限単純グラフに対して未解決である。n≤13n \le 13 頂点のすべてのグラフ（マッケイ、2022年）、木、非連結グラフ、正則グラフ、単閉路グラフ、サボテングラフ、外平面グラフ、極大平面グラフ、および漸近的にほとんどすべてのグラフに対して成り立つことが知られている。次数列、連結性、全域木の個数、固有多項式、彩色多項式やタット多項式などの不変量はデッキから再構成可能であるが、一般の平面グラフや二部グラフについては未解決のままである。

既知の最良の結果

  • 3≤n≤133 \le n \le 13 頂点のすべてのグラフは、デッキ内の同型類の集合だけからでも一意に再構成可能である（マッケイ、2022年）。
  • 木、非連結グラフ、正則グラフ、外平面グラフ、極大平面グラフは再構成可能であり、さらに平面性そのものもデッキから識別可能である。
  • n→∞n \to \infty のとき確率 11 に収束する割合で、ランダムグラフ G(n,1/2)G(n, 1/2) はその任意の 33 個の頂点削除部分グラフによって一意に決定される（ボロバーシュ、1990年）。

使われた手法と限界

手法達成したこと限界
ケリーの数え上げ補題と部分グラフ代数∣V(F)∣<n|V(F)| < n なる任意の部分グラフ FF の各コピーがデッキのちょうど n−∣V(F)∣n - |V(F)| 枚のカードに現れることを利用して FF の出現回数を厳密に決定し、次数列、木、非連結グラフ、およびタット多項式を復元した。ハミルトン閉路のような全域部分グラフ（∣V(F)∣=n|V(F)| = n）を直接数えることができず、対称性の高い2-連結グラフにおいて異なるカード上の断片がどのように組み合わさるかを特定できない。
包除原理とロヴァース・ミュラーの辺数え上げ法辺の部分集合に関する包除原理を通じて自己同型群のサイズを比較することにより、m>nlog⁡2nm > n \log_2 n 本の辺をもつすべてのグラフに対して辺再構成予想を証明した。包除原理の交代和の評価には 2m>n!2^m > n! が必要となるため、頂点再構成の難問が集中する疎な領域 m≤nlog⁡2nm \le n \log_2 n では機能しない。

未解決の問い

  • n≥3n \ge 3 頂点のすべての有限平面グラフ、あるいはすべての有限二部グラフは、その頂点削除デッキから再構成可能か。
  • ハラリィの辺再構成予想は、辺数が 4≤m≤nlog⁡2n4 \le m \le n \log_2 n のすべての疎グラフに対して成り立つか。

参考文献

  1. Paul J. Kelly (1957). A congruence theorem for trees · DOI:10.2140/pjm.1957.7.961
  2. J. A. Bondy, R. L. Hemminger (1977). Graph reconstruction—a survey · DOI:10.1002/jgt.3190010306
  3. Brendan D. McKay (2022). Reconstruction of small graphs and digraphs