Let's say a partial tour is a graph with no degree-three nodes and no ``premature'' loops. That is, it is a subgraph of a tour.
We can view the space of all partial tours as a big DAG where the edges connect a partial tour to another partial tour that includes one additional edge. The weight of a partial-tour-graph edge is the weights of the added edge in the graph.
The empty graph is a partial tour with no incoming partial-tour-graph edges.
What is the out degree of a partial-tour-graph node corresponding to a complete tour? What is the length of any path from the empty graph to a complete tour?
