MST with degree constraints on some node While preparing for an algorithms exam I came across the following problem in a practice test:

Let $G = (V,E)$ be a connected, undirected graph with weighted edges (all weights are rational numbers but not necessarily all unique) and let $v$ be some node in $G$.

Design an algorithm that finds a minimum spanning tree of $G$ where $\deg(v)=2$ if one exists or indicates if there is no such tree.

Full credit will be given for solutions with the same time complexity as Prim's algorithm ($O(|E| + |V|\log |V|)$). Partial credit will be given for solutions whose time complexity is $|V|\cdot$Prim, and minimal credit will be given for solutions with greater time complexity.

The first step in any solution must be to use Prim or Kruskal's algorithm to find the target weight for such an MST. From there, though, I've tried a number of different methods of approaching this problem but all the successful ones require halting an existing MST algorithm before it's done, i.e. prioritizing all $v$'s edges, running Kruskal until $v$''s degree is two, then deprioritizing them and continuing the algorithm, etc.

The problem is that my professor flat-out refuses to accept answers that involve stopping an algorithm in the middle, insisting that this would require one to re-prove the correctness of the entire algorithm.

Does anyone have a solution? The problem has been eating at me for a few weeks now and I haven't been able to find an answer on the internet anywhere. The professor said she won't tell us the answer and I suspect she intends to put this question on this or future exams.

Thanks very much in advance for your time.
Here's an algorithm that just reduces to MST; no need to modify Prim's or some other algorithm. The idea is simple: remove $v$, compute the MSTs of the resulting components of the graph, and then stitch them together with $v$. The interesting case is when removing $v$ doesn't disconnect the graph.

I'll assume the input graph $G$ is connected, although it would not be difficult to generalize this idea to computing a minimum spanning forest. Also, obviously the degree of $v$ needs to be at least 2.

Algorithm

Start by removing $v$ and all incident edges; call this $G'$. Now compute the number of connected components in $G'$. This can be done with DFS or something similar.

More than 2 components:
If $G'$ has more than 2 connected components, no solution is possible.

Exactly 2 components: If $G'$ has exactly two connected components, then we can construct a solution by using $v$ as the "bridge" between the two components: just connect the MSTs of the components with the cheapest edges through $v$.

Exactly 1 component: If $G'$ has exactly one component, we can compute $T' = \text{MST}(G')$, and then we just need to stitch $v$ into $T'$ using two edges.


Find the cheapest edge incident on $v$ and add this to $T'$. Call this $T''$. Now we have a spanning tree, but not necessarily minimum.
Iterate over all other edges incident on $v$. For each of these, we will try to construct a MST where $d(v) = 2$. If we don't find one, then no solution is possible.


Consider some incident edge $(u,v)$ which is not the lightest edge on $v$. 
Observe that if we added this edge to $T''$, it would create a cycle.
If $(u,v)$ is the heaviest edge on this cycle, then skip this edge, because no solution is possible using $(u,v)$.
Otherwise, we can take out the heaviest cycle edge and add $(u,v)$ instead. Now we have a spanning tree where $d(v) = 2$. If this spanning tree is minimum, we're done. (We can determine if a spanning tree is minimum just by computing any $\text{MST}(G)$ and comparing weights. This "reference" MST only needs to be computed once.)



It's not immediately obvious that this is within cost bounds, because for each of $O(|V|)$ edges incident on $v$, we have to compute the heaviest edge in the tree on the path between $v$ and some other vertex $u$. However, these "path queries" are well studied in the literature, and can be computed in $O(\log|V|)$ by preprocessing $T''$ into a balanced lookup structure. Some examples include binary lifting, Miller-Reif rake/compress tree contraction, and Sleator-Tarjan link/cut trees. The link/cut trees are actually far more general: they handle dynamic trees too! But here we only need to preprocess a static tree, i.e. $T''$.



Edit: My original idea was to do the following, which doesn't work (thank you @VladislavBezhentsev for pointing this out in the comments!). It doesn't work because, while we know that the cheaper of $e_1$ and $e_2$ is certainly in the MST (by the cut property), it's not necessarily true that the heavier of the two edges is!


  (Incorrect idea): Find the two cheapest edges $e_1$ and $e_2$ that are incident on $v$. Add $e_1$ and $e_2$ to $T'$: this creates a cycle. If the largest edge on this cycle is either $e_1$ or $e_2$, no solution is possible. Otherwise, remove the largest edge on the cycle.