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\ge 10$. It is also proved that if two graphs of order $n\ge 6$ have $n-2$ cards in common, then the number of edges in them differs by at most one.