Given an undirected graph $G=(V,E)$, and vertex $v\in V$ and a number $k\in \mathbb{N}$, find an algorithm to find whether there exists a spanning tree of $G$ in which $v$ satisfies $d(v)=k$
I've narrowed the solution to 3 situations, in $G$: $d(v)<k , \\d(v)=k\\d(v)>k$
When $d(v)<k$, it is clear that there cannot exist a spanning tree of $G$ such that $d(v)=k$, since $d(v)$ was never of value $k$ to begin with.
When $d(v)>k$, we know that we can create a graph $G'$ in which we remove a finite amount of edges $i$ in such a matter that we reduce $d(v)$ to be $k$, and check whether $G'$ is connected or not (we can use BFS), since $d(v)\leq |V|$, the complexity would be $O(|V|\cdot (|V|+|E|))$, however I feel this is extremly inefficient.
For the case where $d(v)=k$ in $G$, I am uncertain on how to proceed.
EDIT: I've managed to update the case where $d(v)>k$ to be in linear time:
if $d(v)>k$, we'll have to remove edges from the graph.
We'll perform $DFS$ on $v$, since $d(v)>k$ there will be back edges, we can (in linear time) count how many back edges are going into(or out of) $v$, if the number of back edges is greater than $m-k$ where $|E|=m$, we can remove $m-k$ back edges from $G$, if the number of back edges is smaller than $m-k$, there cannot be a spanning tree in which $d(v)=k$.
The updated solution to the case was given to me by a colleague, I dont completely understand it yet I am trying to wrap my head around it.
About the case where $d(v)=k$, I am still uncertain.