Reconstruction of triangle-free diameter-2 graphs with connectivity at least 4, and an edge-reconstruction analogue of the diameter reduction

The Reconstruction Conjecture asserts that every graph on at least three vertices is determined up to isomorphism by the multiset of its vertex-deleted subgraphs (its deck); it is known to reduce to 2-connected graphs of diameter 2, or of diameter and co-diameter both 3 (the classes $\mathcal{G}_2$ and $\mathcal{G}_3$). For triangle-free graphs in this critical family, all vertex-deck connectivity cases are settled except one: Clifton, Liu, Mahmoud, and Shantanam proved the $\kappa=3$ case in $\mathcal{G}_2$ and all $\kappa\ge 3$ cases in $\mathcal{G}_3$, explicitly leaving open whether every triangle-free diameter-2 graph with vertex connectivity at least 4 is reconstructible; a positive answer would confine all potential counterexamples within the critical family to graphs containing triangles, while a negative answer would refute the Reconstruction Conjecture itself. The same paper settled edge reconstruction for all triangle-free $\mathcal{G}_2$ and $\mathcal{G}_3$ graphs, but flagged a second open direction: obtaining an edge-reconstruction analogue of the diameter reduction, i.e., a theorem restricting the graphs critical for the Edge Reconstruction Conjecture to $\mathcal{G}_2\cup\mathcal{G}_3$, which is obstructed because the complement-deck recovery used in the vertex-deck reduction fails for edge-decks. Both components remain open.

Background

All graphs here are finite, simple, and undirected. The deck of a graph $G$ is the multiset $\mathcal{D}(G)=\{G-v: v\in V(G)\}$ of its vertex-deleted subgraphs, called cards; $G$ is reconstructible if every graph whose deck equals $\mathcal{D}(G)$ is isomorphic to $G$. The Reconstruction Conjecture (RC), also called the Kelly–Ulam conjecture, asserts that every graph on at least three vertices is reconstructible; it is one of the most prominent open problems in graph theory and has been computationally verified for all graphs on at most eleven vertices (McKay, 1997). Write $\overline{G}$ for the complement (the graph on the same vertices with precisely the non-edges of $G$), $\operatorname{diam}(G)$ for the diameter (largest distance between two vertices), and $\kappa(G)$ for the vertex connectivity (the size of a smallest set of vertices whose deletion disconnects the graph or leaves a single vertex); a graph is 2-connected if it has at least two vertices and no cut vertex.

A chain of reductions narrows where a counterexample to the RC could live. Yang (1988) proved that the RC holds if and only if every 2-connected graph is reconstructible. Gupta, Mangal, and Paliwal (2003) proved that the RC holds if and only if it holds for every connected graph of diameter 2, or of diameter and co-diameter both 3; the engine of their proof is that $G$ is reconstructible if and only if $\overline{G}$ is, together with recovery of the deck of $\overline{G}$ from the deck of $G$. Ramachandran and Monikandan (2009) combined the two, proving that the RC is true if and only if every 2-connected graph in $\mathcal{G}_2\cup\mathcal{G}_3$ is reconstructible, where $\mathcal{G}_2=\{G: \operatorname{diam}(G)=2\}$ and $\mathcal{G}_3=\{G: \operatorname{diam}(G)=\operatorname{diam}(\overline{G})=3\}$. Thus any counterexample to the RC may be assumed to be 2-connected and to lie in $\mathcal{G}_2\cup\mathcal{G}_3$.

Within this critical family, attention turned to triangle-free graphs (graphs containing no 3-cycle). Monikandan and Balakumar (2012) proved that triangle-free graphs in $\mathcal{G}_2\cup\mathcal{G}_3$ with connectivity exactly 2 are reconstructible, and asked whether the result extends to connectivity at least 3, remarking that a positive answer would restrict the remaining RC-critical graphs to those containing triangles. Clifton, Liu, Mahmoud, and Shantanam (2022 preprint; Discrete Mathematics 2024) gave a partial solution: every triangle-free graph in $\mathcal{G}_3$ with $\kappa\ge 3$, and every triangle-free graph in $\mathcal{G}_2$ with $\kappa=3$, is reconstructible. By the authors' own accounting, this leaves exactly one vertex-deck case open: triangle-free graphs in $\mathcal{G}_2$ with $\kappa\ge 4$.

The edge analogue replaces vertex deletion by edge deletion. The edge-deck of $G$ is the multiset $\mathcal{ED}(G)=\{G-e: e\in E(G)\}$ of edge-cards, and $G$ is edge-reconstructible if every graph with the same edge-deck is isomorphic to it. The Edge Reconstruction Conjecture (ERC), proposed by Harary, states that every graph with at least four edges is edge-reconstructible. Greenwell (1971) proved that the (vertex) deck of $G$ is recoverable from the edge-deck when $G$ has at least four edges and no isolated vertices, so such graphs are edge-reconstructible whenever they are reconstructible. Clifton et al. proved that triangle-free graphs in $\mathcal{G}_2$ and in $\mathcal{G}_3$ are edge-reconstructible outright, so the edge-deck side of the triangle-free program is complete. What has no edge counterpart is the reduction theorem itself: the proof that the RC reduces to $\mathcal{G}_2\cup\mathcal{G}_3$ passes through recovery of $\mathcal{D}(\overline{G})$ from $\mathcal{D}(G)$, and this recovery has no edge-deck analogue, so no diameter-based reduction of the ERC is currently known.

Problem Statement

Let $\mathcal{G}_2=\{G: \operatorname{diam}(G)=2\}$ and $\mathcal{G}_3=\{G: \operatorname{diam}(G)=\operatorname{diam}(\overline{G})=3\}$, and let $\kappa(G)$ denote vertex connectivity. The problem, as left open by Clifton–Liu–Mahmoud–Shantanam, has two linked components, both of which form the research target.

(1) Vertex-deck case. Determine whether every triangle-free graph $G\in\mathcal{G}_2$ with $\kappa(G)\ge 4$ is reconstructible from its deck $\mathcal{D}(G)$. This is the only remaining connectivity case for triangle-free graphs in the family critical for the Reconstruction Conjecture: a positive answer, combined with the settled cases $\kappa=2$ and $\kappa=3$, would confine all potential counterexamples to the RC among 2-connected graphs in $\mathcal{G}_2\cup\mathcal{G}_3$ to graphs containing a triangle; a negative answer — an explicit pair of non-isomorphic triangle-free diameter-2 graphs with connectivity at least 4 sharing a deck — would refute the Reconstruction Conjecture itself.

(2) Edge-deck reduction. Establish an edge-reconstruction analogue of the diameter reduction: a theorem, similar to the vertex-deck reduction stated above, that the Edge Reconstruction Conjecture is true if and only if every graph in $\mathcal{G}_2\cup\mathcal{G}_3$ with at least four edges is edge-reconstructible — that is, a result restricting the class of graphs critical for proving the ERC to those which lie in $\mathcal{G}_2\cup\mathcal{G}_3$. The known obstruction is that the vertex-deck reduction relies on recovering $\mathcal{D}(\overline{G})$ from $\mathcal{D}(G)$, which is not true for edge reconstruction; the source authors judge such a result unlikely to be proved using techniques similar to those used in the proof of the vertex reduction, while noting that the advantages of having such a result merit further investigation.

The two components serve one common objective: completing the diameter-and-triangle-based reduction program for the two reconstruction conjectures, that is, determining exactly which triangle-free and bounded-diameter graphs must still be examined when searching for counterexamples to them.

References

1. Alexander Clifton, Xiaonan Liu, Reem Mahmoud, Abhinav Shantanam, Reconstruction and edge reconstruction of triangle-free graphs, Discrete Mathematics 347(2), Article 113753 (2024), DOI 10.1016/j.disc.2023.113753, arXiv:2210.00338, https://arxiv.org/abs/2210.00338
2. S. Monikandan, J. Balakumar, Reconstruction of bipartite graphs and triangle-free graphs with connectivity two, Australasian Journal of Combinatorics 53 (2012) 141–150, zbMATH 6077842 (AN 1256.05154), https://ajc.maths.uq.edu.au/pdf/53/ajc_v53_p141.pdf, https://dblp.org/rec/journals/ajc/MonikandanB12
3. S. Ramachandran, S. Monikandan, Graph reconstruction conjecture: reductions using complement, connectivity and distance, Bulletin of the Institute of Combinatorics and its Applications 56 (2009) 103–108, zbMATH 5572982 (AN 1175.05096), https://zbmath.org/?q=an%3A5572982
4. S. K. Gupta, Pankaj Mangal, Vineet Paliwal, Some work towards the proof of the reconstruction conjecture, Discrete Mathematics 272 (2003) 291–296, DOI 10.1016/S0012-365X(03)00198-5, https://doi.org/10.1016/S0012-365X(03)00198-5
5. D. L. Greenwell, Reconstructing graphs, Proceedings of the American Mathematical Society 30 (1971) 431–433, DOI 10.1090/S0002-9939-1971-0286699-3, https://doi.org/10.1090/S0002-9939-1971-0286699-3
6. Yongzhi Yang, The reconstruction conjecture is true if all 2-connected graphs are reconstructible, Journal of Graph Theory 12(2) (1988) 237–243, DOI 10.1002/jgt.3190120214, https://doi.org/10.1002/jgt.3190120214
7. Brendan D. McKay, Small graphs are reconstructible, Australasian Journal of Combinatorics 15 (1997) 123–126, https://ajc.maths.uq.edu.au/pdf/15/ocr-ajc-v15-p123.pdf, https://dblp.org/rec/journals/ajc/McKay97
8. J. Antony Aravind, S. Monikandan, A Reduction of the Reconstruction Conjecture using Domination and Vertex Pair Parameters, arXiv:2601.00620 (2026), https://arxiv.org/abs/2601.00620
9. Maxine E. Calle, Julian J. Gould, A combinatorial $K$-theory perspective on the Edge Reconstruction Conjecture in graph theory, arXiv:2402.14986 (2024), https://arxiv.org/abs/2402.14986
10. Irene Heinrich, Masashi Kiyomi, Yota Otachi, Pascal Schweitzer, Interval Graphs are Reconstructible, arXiv:2504.02353 (2025), https://arxiv.org/abs/2504.02353