分野：図形
頂点と辺で構成されたものをグラフという．辺は頂点を結ぶ．頂点がn個のグラフGがあると，Gから1頂点とその頂点から出ている辺を取り除いたグラフ（部分グラフ）がn個考えられる．n個のグラフから，もとのグラフGを再構成できるかが知られていない．反例があるなら，n個のグラフから2種類以上のグラフが考えられる例を挙げればよい．例えば，以下のグラフは5頂点あり，5個の部分グラフH1,H2,H3,H4,H5が考えられる．グラフH1,H2,H3,H4,H5が与えられたら，グラフGを再構成できるかという問題である．
未解決問題
n個の頂点を除去したグラフが与えられたら，もとのグラフを一意に再構成できるか．
練習問題
上の例は，どう考えたら再構成できるか考えよう．
問題の変更
辺の除去（edge reconstruction conjecture）ではどうか．こちらも未解決問題が知られている．
関連内容：
キーワード：グラフ理論
英語キーワード：graph reconstruction
参考文献：John Clark, Derek Allan Holton（1991）A FIRST LOOK AT GRAPH THEORY