Pairs of Graphs Having \(n-2\) Cards in Common

Abstract

For a vertex \(v\) of a graph \(G\), the unlabeled subgraph \(G-v\) is called a \({card}\) of \(G\). We prove that the connectedness of an \(n\)-vertex graph \(G\) and the presence of isolated vertices in \(G\) can be determined from any collection of \(n-2\) of its cards. It is also proved that if two graphs on \(n \geq 6\) vertices with minimum degree at least two have \(n-2\) cards in common, then the numbers of edges in them differ by at most one.