Dense graphs and edge reconstructions (Q1375698)

Nash-Williams proved that if a graph \(G\) is not edge reconstructible, then for all \(A \subset E(G)\), \(|A|\equiv |E(G)|\pmod {2}\) there is a permutation \(\phi\) of \(V(G)\) such that \(E(G) \cap E(G\phi)=A\). The author shows that the previous result cannot settle the edge reconstruction conjecture by exhibiting an arbitrarily large graph which satisfies the Nash-Williams condition but still \(e \geq n \lfloor \sqrt{1/2 \log n} \rfloor\), where \(e\) and \(n\) stand for the number of edges and vertices, respectively.