On 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 number of isolated vertices and the number of components of an \(n\)-vertex graph \(G\) can be determined from any collection of \(n-2\) of its cards for \(n \geq 10\). It is also proved that if two graphs of order \(n \geq 6\) have \(n-2\) cards in common, then the number of edges in them differs by at most one.