Minimum Degree Spanning Tree Without Restricting Vertices Searched
This is not an answer, but some experimental evidence on why I think this might be an $OPT+1$ approximation.
I wrote some python code that runs the local search algorithm (without restricting the vertices searched) and solves the problem optimally with ILP. I tried it on thousands of small random graphs and the local search was always $OPT$ or $OPT+1$. Here is the code:
import networkx as nx
from pulp import *

def local_search(G):
    T = nx.algorithms.tree.mst.minimum_spanning_tree(G)

    while True:
        noChange = True
        for w in G:
            for u,v in G.edges():
                Tset = set(T.edges())
                if (u,v) not in Tset:
                    T.add_edge(u,v)
                    C = nx.algorithms.cycles.find_cycle(T)
                    T.remove_edge(u,v)
                    C_vertices = set([x for y in C for x in y ])
                    if w in C_vertices and T.degree[w]&gt;=max(T.degree[u], T.degree[v])+2:
                        T.add_edge(u,v)
                        for x,y in C:
                            if x==w or y==w:
                                T.remove_edge(x,y)
                                break 
                        noChange = False
        if noChange:
            break
    return max([T.degree[u] for u in G]), T

def opt_soln(G):
    prob = LpProblem(&quot;The Minimum Degree Spanning Degree&quot;,LpMinimize)
    z = LpVariable(&quot;maxIndegree&quot;,1,None,LpInteger)
    variables = {
        tuple(sorted([u,v])) : LpVariable(f&quot;x_{(u,v)}&quot;,0,1,LpInteger) for u,v in G.edges()
    }
    vertex_to_edges = {
        u : [variables[tuple(sorted([u,v]))] for v in G.neighbors(u)] for u in G
    }
    prob += z
    prob += lpSum(variables.values()) == (len(G)-1)
    for u in G:
        prob += lpSum(vertex_to_edges[u]) &lt;= z
    prob.solve()
    return value(prob.objective)


tries = 1000
for _ in range(tries):
    n = 34
    p = 0.1
    d = 10
    G = nx.generators.random_graphs.fast_gnp_random_graph(n, p)
    #G = nx.generators.random_graphs.random_regular_graph(d, n)
    if not nx.is_connected(G):
        continue 
    delta_T, T = local_search(G)
    delta_star = opt_soln(G)
    if delta_T-  int(delta_star)&gt;1:
        print(delta_star, delta_T)
    #nx.draw(T)