# Graph Theory and Minimum Spanning Trees

(1) Given a connected graph G of p vertices. Is it possible to find randomly a tree T of G then assume the end vertices of T to be a set S having Steiner tree T. (2) Given a set S of k-vertices, is it possible to construct a graph G of p vertices(p>k) containing S such that G contains a Steiner tree T of S. Is the above problems are equivalent to the Steiner tree problem?

-
(3) Is this homework? (4) Where did you get stuck? (5) What's a Steiner tree? – Yuval Filmus Feb 9 '12 at 14:41
I faced the problem during my work in graph theory. The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. – Herish Feb 9 '12 at 14:51

(1) Suppose $G$ is a complete graph on $p=4$ vertices at the corners of a square. If $T$ is any subtree with 3 or 4 vertices then $T$ will not be a Steiner tree for its "end vertices".
(2) Given $S$, the Steiner tree $T$ of $S$ is itself a graph containing a Steiner tree of $S$.