On Reconstructing Graphs from $n-2$ Cards

Abstract

Let $G$ and $H$ be graphs on $n+2$ vertices $\{u_1,u_2,\dots ,u_n,x,y\}$ such that $G–u_i\cong H–u_i$, for $i=1,2,\dots ,n$. Recently, Ramachandran, Monikandan, and Balakumar have shown in a sequence of two papers that if $n\ge 9$, then $|\epsilon (H)–\epsilon (G)|\le 1$. In this paper, we present a simpler proof of their theorem, using a counting lemma.