MathLabs

未解决问题，组合数学与离散数学，1941年提出

图重构猜想

未解决

设 GG 与 HH 是顶点数 n≥3n \ge 3 的有限简单无向图。若它们的牌组——即删去单个顶点所得无标号诱导子图构成的多重集 {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 时，随机图 G(n,1/2)G(n, 1/2) 以趋于 11 的概率由其任意 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