Hints: Sasha and a Walk in the City

Given a connected induced subgraph, what is the size of the minimal set of vertices required to uniquely construct this subgraph. Not just the size, the minimal set of vertices required is also fixed. Can you figure out what those are?

The leaf vertices (or to be more precise, the degree-1 vertices) are absolutely critical in determining uniqueness. This is because, if you lose track of leaf vertices, the remaining subgraph would still be connected, and you would not be able to figure out if the leaf vertex is supposed to be there or not.

Once you have all the leaf vertices, you can make the subgraph connected by adding all the vertices that lie on the path between these leaf vertices.

The minimum size required to reconstruct this subgraph is equal to the number of degree-1 vertices.

In fact, the collection of all degree-1 vertices is the minimal set required for unique construction of the subgraph.

Given a connected induced subgraph, figure out a unique coloring strategy that avoids a path containing more than 2 black vertices.

Color all the degree-1 vertices of this subgraph in black and the rest of the vertices in white. Note that that all other vertices except the degree-1 vertices were added to the subgraph only because it was on a path between 2 vertices. Hence, if we color those black, the path would now contain 3 black vertices.

Given a coloring, figure out a strategy to uniquely construct a connected induced subgraph.

Treat all the black vertices as degree-1 vertices and then expand the set to make it connected.

Why is such a construction always possible? We just need to prove that the set of black vertices represent a set of minimal leaf vertices.

A set does not contain minimal leaf vertices if it has u, v and w such that w lies on the path between u to v. However, this is not possible in our case, since this was a valid coloring, so the path cannot contain 3 black vertices.