Local search to find minimum degree spanning tree
No, we cannot always find an edge $e$ to add when $\Delta(T) &gt; \Delta^*$.

 

The graph above was drawn at https://graphonline.ru/en 


Here is an counterexample. Let $G$ be the 3-regular graph on the right side that has 14 vertices and 21 edges. Let $T$ be the spanning tree that consists of all the edges in bold. That is, $T$ has all the edges in $G$ except the innermost 7 edges and the edge at the top right. The graph on the left side shows a hamiltonian path of $G$. That is, $\Delta(T)=3$ and $\Delta^*=2$.

Let $e$ be an edge not in $T$. If we add $e$ to $T$, the resulting cycle $C$ contains at least two non-adjacent vertices of degree 3 in $T$. If we further delete any edge in $C$ incident to a vertex in $C$ with the highest degree 3, we obtain graph $T'$.  There is at least one vertex of degree 3 in $T'$. That is, the maximum degree of vertices in $V(C)$ in $T'$ is 3.