this is for holding javascript data
Jeremy Ting edited q2.tex
almost 10 years ago
Commit id: 4b8472d737c61711d25f19af1ab7e7957dd83f66
deletions | additions
diff --git a/q2.tex b/q2.tex
index 2a20797..16bb102 100644
--- a/q2.tex
+++ b/q2.tex
...
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.
\textbf{Showing \textit{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.