How to build a subgraph?

Question

Programming

Good day. I apologize for the possibly clumsy statement of the problem, but how can I ..
There is a connected undirected graph. The nth number of vertices is randomly selected from this graph (n is much less than the initial number of vertices in the graph, if that matters). It is necessary to get a subgraph from the original graph that will contain all the selected/specified n vertices, will also remain connected, but the number of vertices from the original graph that are not included in n, but included in the subgraph, to maintain connectivity, will be minimal.
Surely such a task already has a solution, tell me, please, where to dig? If there is no link to the description, at least just the name of the algorithm.

Answer 1

Exclude from the graph all vertices not included in the selection, replacing them with edges with added weight. Those. let's say there is a vertex A, edges AB=1, AC=1, AD=2. The vertex and edges are replaced with edges: BC=2, BD=3, CD=3
Then find the minimum spanning tree. You can take the Kruskal algorithm, the description is on the wiki: https://ru.wikipedia.org/wiki/Kruskal_Algorithm