# Steiner tree problem in graphs of diameter 3

I have an unweighted undirected graph $$G(V, E)$$ of diameter 3 and a subset $$T\subseteq V$$ of these vertices. I want to find the minimum tree $$(V', E')$$ that contains all vertices in $$T$$, minimizing the number of nodes $$|V'|$$.

Is it true that $$|V'|\le 2|T|$$? If $$G$$ is of diameter 2 it is easy to prove that this is true. Also for diameter 4, it is not true always since we can take a path graph of 5 vertices with $$T$$ as two leaves.

This is an interesting question.

It is not true that $$|V'|$$ is always less than or equal to $$2|T|$$. Here is the smallest example of $$G$$ and $$T$$ where $$|V'|$$ must be greater than $$2|T|$$.

Graph $$G$$ as depicted above has 9 vertices $$A,A_1,A_2,B,B_1,B_2,C,C_1,C_2$$ and 12 edges $$AA_1, A_1A_2, A_2A,$$ $$BB_1,B_1B_2,B_2B,$$ $$CC_1, C_1C_2, C_2C,$$ $$A_1B_2, B_1C_2, C_2A_1$$. It is easy to check the diameter of $$G$$ is 3.

Let $$T=\{A,B,C\}$$. Suppose $$T'=(V',E')$$ is a minimal tree in $$G$$ that spanns $$T$$.

• If $$V'$$ contains all 9 vertices, then $$|V'|=9$$.
• Otherwise, WLOG, assume $$V'$$ does not contain $$A_1$$. If anyone of $$A_2$$, $$C_1$$, $$C_2$$ and $$B_1$$ is not in $$T'$$, then $$A$$ and $$B$$ will not be connected in $$T'$$. Since $$A$$ and $$B$$ are connected in $$T'$$, all of those 4 vertices must be in $$T'$$. So $$|V'|\ge3+4=7$$.

So $$|T'|\gt 6= 2|T|.$$

Exercise 1. Verify that the following two graphs are also examples where $$|V'|$$ must be greater than $$2|T|$$ with $$T=\{A, B, C\}$$

Exercise 2. (less than 1 minute) If $$|T|=3$$, then $$|V'|\le7$$.

Exercise 3. Let $$n\ge3$$. Construct $$G$$ and $$T$$ such that $$G$$ is connected of diameter 3, $$|T|=n$$ and $$|V'|\gt 2|T|$$. (Hint, imitate the simpler example in exercise 2.)