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.