A.
To solve this problem we can just solve the traveling salesman problem. In addition, because this is just a MST we do not need this to be a cycle. So we can delete the edge with the highest value, and that will destroy the cycle, but we will end up with a MST since each node has a max degree of 2.
So we can solve the traveling salesman problem using dynamic programming.
Subproblems will be subsets of the vertices \(S\) from \((1,2,....,n)\) that includes the origin and a specific node j. Let \(C(S,j)\) be the length of the shortest path visiting each node in S starting at 1 and stopping at \(j\).
So \(C(S,j)\) = \(min(C(S-j,i)+d_{ij})\) for each \(i\), where \(i\) are all the neighbors of \(j\).
\(d_{ij}\), is the distance from \(i\) to \(j\). You must find a path to a neighbor \(i\), and then add it to the cost \(d_{ij}\).
This will give us solution of Traveling Salesman Problem so you get the lowest cost tour of this graph. So all we have to do is delete the most expensive edge in the tour. That will give us the minimum spanning tree with degree 2.
Showing that it is NP-Complete:
If there are at most 2 connections for each node in a spanning tree in \(G\) then \(G\) must also have a Rudrata Path. The Rudrata path will be exactly the graph of \(G\) because a spanning tree hits all the nodes so if we follow this path we find the Rudrata path.
If you can’t find a graph with at most 2 connections per node and is a spanning tree in \(G\) then a Rudrata path does not exist in \(G\). Assume that there is not a spanning tree in \(G\) with at most 2 connections per node but there is a Rudrata path in \(G\). A Rudrata Path visits all the nodes in \(G\) and has no cycles. Thus the degree of each node in the Rudrata path is at most 2 which would also be a spanning tree with at most 2 connections per node which is a contradiction.
B.
If we have the solution for TSP l then we can find the solution to the 2 degree MST easily because \(TSP=MST\) with a degree of 2.
For \(d>2\):
Look at all the vertices that only have one vertex coming out of it. Then check all the edges leaving said vertex and then find the shortest one if it is shorter than the one already in the MST, swap them and that will decrease the total cost. Then continue to look at all the vertices with 1 edge and continue this process. Before you add an edge, make sure the vertex you are going to add it to only has a \(d-1\) degree so when you add the edge the degree will be a max of \(d\).
Then for the nodes with more than one edge coming out of it we have to look at cuts.
Consider a graph where there is a node E, that has outward edges to 3 other different nodes A,B,C. Compare the edge that exists in the MST and is going into a node A,B, or C, with the ones that are going into A,B, or C, but are not in the MST. If there exists an edge not in the MST which is cheaper and it wont break the degree constraint, then swap them (them being the edge in the MST and the one that isnt).