Show that a minimal solution has degree at most 2

Question

Given a graph $G=(V,E)$, and a set $T\subseteq V$ of terminals, we say that $S \subseteq V\setminus T$ is feasible if $G[T\cup S]$ is connected.

In other words, a feasible solution is a set of non-terminals $S$ so that all the terminals can pairwise reach each other in $G[T \cup S]$.

I also know the following about my graph:

1. Each non-terminal node is incident to at most 2 terminals.
2. $T$ is an independent set.

Now suppose I have a minimal feasible solution $S$. This means that removing any node from $S$ would disconnect some pair of terminals.

Is it true that the average degree of terminal nodes in $G[T \cup S]$ is at most 2?

I believe this to be true, and I can't find a counterexample. But I am having trouble proving it. Thanks for any help!!!

Answer 1

Edit: (an even simpler counter example) Here is a counter example to your problem : Let $t_1, t_2, ..., t_5, T_1, T_2$ be seven terminal, $s_1, s_2, ..., s_5, s_1', s_2', ..., s_5'$ be vertices from $S$. We define the edges $t_is_i, s_is_i'$ for $i=1...5$, and the edges $s_iT_j$, for $i=1...5, j=1...2$. The resulting graph have a degree of 15, and only 7 terminals.

Edit :
I adapted my proof to show that the average degree is below 3.

---

We will prove that the sum of the degrees of $T$ is less than $3|T|-4$ (|T|>2) for each feasible solution where each vertex of $S$ is a cut vertex. (The optimal solution must verify this, otherwise, this would contradict minimality). We will prove it by induction on the size of $|T|$ in $H = G[T\cup S]$.

The initialization is true for $|T|=2$, because the sum of the degrees must be $2$ in any minimal solution. For $|T|=1$, the sum of the degrees is $0=|T|-3$.

Let $H = G[T\cup S]$ be a graph. If $|T| > 2$, $H$ must contain at least a vertex $v$ in $S$ (because $T$ is an independent set). $v$ is a cut vertex of $H$. It's deletion creates at least two connected graphs $H_1, H_2, ..., H_n$, which contains sets $T_1, T_2, ..., T_n$ of terminals, each one non-empty, and $S_1, S_2, ..., S_n \subset S$.

Let $A_i \subset S_i$ be the set of vertices such that $H_i\setminus A_i$ is a minimal connected graph spanning $T_i$. The deletion of any vertex of $A_i$ keeps all the vertices of $T_i$ connected in $H_i$. (otherwise, $H\setminus A_i$ would not be connected). If a vertex of $A_i$ is not a cut vertex of $H_i\cup \{v\}$, then its deletion creates one connected component containing $T_i$, and another one containing $v$ (If a connected component contains none of $T_i$ or $v$, then it contains no terminal, and $H$ is not minimal). Lets suppose that there exist two distinct vertices $a_1, a_2 \in A_i \cup \{v\}$ neighbors of a terminal in $H_i$. At least one of these (say $a_1$) have a path to $v$ not going through the other one. If we delete $a_2$, then $H_i$ is connected ($v$ connect $a_1$ which connect a terminal, so $v$ can't be a cut vertex), and so $H$. This contradict minimality of $H$, so only one vertex of $A_i\cup \{v\}$ is neighbor to a terminal in $T_i$. The degree of the terminals between $H_i\setminus A_i$ is at most 2.

We apply the recurrence on each $H_i\setminus A_i$, which are minimal graphs. Each $H_i$ brings a degree of at most $3|T_i|-4+2 = 3|T_i|-2$ if $|T_i| > 1$. If $|T_i|=1$, it also brings a degre of at most $3|T_i|-2$. Summing all of this gives $3|T|-2n \leq 3|T| -4$ because $n\geq 2$.