A vertex-deleted subgraph (or card) G-v of a graph G is obtained from G by deleting the vertex v and all edges incident with v. We prove that a connected graph G on n vertices with at least n-3 of its cards isomorphic is either regular or bidegreed or belongs to one of six mutually disjoint families of T-graphs (where T-graph is a graph which is neither regular nor bidegreed). We use this to prove that such graphs are reconstructible.
展开▼
