1. Hat die Eingabe zwei Knoten, die nicht durch einen Pfad verbunden sind, so besitzt die Eingabe keine Tour. Ein Besuchen aller Knoten ist dann nur durch mehrere Touren möglich. Das Bestimmen der Zusammenhangskomponenten (die wir uns als isolierte Straßennetze vorstellen können) ist aber effizient mittels modifizierter Tiefen- oder Breitensuche möglich. Wir können dann darauf abzielen, für jede Zusammenhangskomponente eine eigene Tour zu ermitteln.
2. Besteht die Eingabe aus nur einer einzigen Zusammenhangskomponente, bei denen zwei Knoten a und b nicht durch eine Kante verbunden sind, können wir unterstellen, dass wir dennoch auf einem kürzesten Weg von a nach b fahren können. Diesen kürzesten Weg sehen wir dann als die fehlende Kante an. In einer ermittelten Tour wird diese künstliche Kante dann wieder durch einen entsprechenden kürzesten Weg ersetzt3 . Die Bestimmung der kürzesten Wege für alle Paare von Knoten ist z.B. durch den Algorithmus von Floyd-Warshall4 oder durch ggf. mehrfache Anwendung des Algorithmus von Dijkstra5 effizient möglich.
1. Aus einer Tour lässt sich durch Entfernen einer Kante ein Teilgraph herstellen, der kreisfrei und zusammenhängend ist und alle Knoten enthält. Ein solcher Teilgraph ist ein spannender Baum. Seine Gesamtlänge kann nicht kleiner sein als die eines minimal spannenden Baums.
2. Aus einem spannenden Baum lässt sich eine Tour herstellen, in der Knoten mehrfach besucht werden dürfen. Dazu traversieren wir den spannenden Baum so, dass jede Kante zweimal verwendet wird. Die Gesamtlänge, der so entstehenden Tour, ist das Doppelte der Gesamtlänge des zugrundeliegenden spannenden Baums. Fig. 3. zeigt eine solche Tour mit Kosten 20 für den MST aus Fig. 2.
3. Aufgrund der vorausgesetzten Dreiecksungleichung wird eine wie in 2. ermittelte Tour nicht länger, wenn an einem beliebigen Knoten gestartet wird und bereits besuchte Knoten übersprungen werden. Fig. 4 zeigt eine solche aus dem MST in Fig. 3 gewonnene Tour mit Kosten 17.