A graph (on at least 3 vertices) is uniquely determined by the multiset of all possible vertex deletions of it.
Determined up to isomorphism, that is. A vertex deletion of a graph is the graph you get out of deleting some vertex and all the edges incident to it. You have to say at least 3 vertices because it's just not true for 2! There are only two graphs on 2 vertices, * * and *→*, which both have {*,*} as their multiset of vertex deletions.
There's a related (stronger) conjecture,
A graph (on at least 4 vertices) is uniquely determined by the set of all possible vertex deletions of it
And there you can see the 4 is necessary, because the multiset of vertex deletions of
* *→* is {* *, * *, *-*}, and that of *-*-* is {* *, *-*, *-*}, and these collapse to the same set if we ignore multiplicities, {* *, *-*}.
Here's a question I thought of:
Given n, what is the smallest pair of graphs G and H such that ||D(G) ∩ D(H)|| ≥ n, where D(G) is the set of vertex deletions of G?
I can't even think of graphs such that ||D(G) ∩ D(H)|| ≥ 3! I sort of expect they must exist, though. The thought of there being a constant upper bound on ||D(G) ∩ D(H)|| for all G and H seems absurd. I bet this could be refuted by playing with the output of Nauty, which contains tools for generating all nonisomorphic graphs over n vertices, and testing graph isomorphism.
---
Ah, thought of a pair over four vertices just by pencil-and-paper brute force.
o--o | o--o--o o--o | | o--o--o
both possess vertex deletions
o--o o--o | | o--o o o | o--o--o
and then each has one more that distinguishes them.
---
Another example that is smaller with respect to jointly how many distinct vertex deletions exist of of G (3) and H (4):
G H o---o o---o / \ / \ / \ / \ o---o---o o---o o
Maybe the right question to ask is how small you can get the distinct sets of vertex deletions of the pair
such that their intersection is at least n big. In this case (||D(G)||,||D(H)||) = (n,n+1) for ||D(G)∩D(H)||=n is as close as you can get without violating the second conjecture above (which violation would require (n,n)), and this does in fact obtain for n=1,2,3.
