# Finding existence(or non existence) of spanning tree with a specific degree on a specific vertex

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$$

When $$d(v), 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.

• Why can't you just run an MST algorithm in case $d(v) = k$? Or better yet if you do not need an MST, a BFS starting from $v$ to see if the graph is connected which would imply that there is a tree that spans all vertices, hence an MST algorithm will find one that minimizes the total weight. Commented Jan 14, 2023 at 13:31
• The question asks for a linear time complexity in all cases, I've edited my answer for the case in which $d(v)>k$ with a linear solution. MST finding algorithms run in $O(nlogn)$ Commented Jan 14, 2023 at 13:35
• Please see my edited comment. And maybe include that running time requirement in the question Commented Jan 14, 2023 at 13:36
• @Russel Please note that this problem doesnt necessarily discuss MSTs, but spanning trees in general. Commented Jan 14, 2023 at 13:42
• So I think running BFS starting from $v$ and checking if all vertices are reachable will suffice when the degree of $v$ in $G$ is $k$, since a BFS will force all edges of $v$ to be part of the BFS tree rooted at $v$, which will be a spanning tree if all vertices will be reached from $v$ Commented Jan 14, 2023 at 13:45

First, verify that $$G$$ is indeed connected, otherwise say no.
Second, if $$G - v$$ (the graph after deleting $$v$$) has more than $$k$$ components, we can say no.
Pick any $$k$$ neighbors of $$v$$ with the restriction that you pick at least one from each component of $$G-v$$ and mark them. The edges from $$v$$ to these marked vertices are in the spanning tree.
For each connected component $$C$$ of $$G-v$$, pick a marked vertex $$x$$. Run a DFS from $$x$$ and pick the edges you traverse as long as you see an unvisited vertex. If you meet a visited vertex, you ignore the edge. If you meet a marked vertex, simply do not put that edge into the spanning tree.