Die s-t-MinCuts aller Paare von Knoten s,t eines ungerichteten und gewichteten Graphen G können durch einen Strukturbaum B repräsentiert werden, der mindestens die Knoten des Graphen G enthält. Der Wert eines s-t-MinCuts ergibt sich dabei als Minimum der Kantengewichte des eindeutigen Weges in B, der s und t miteinander verbindet; der MinCut selbst ergibt sich dabei durch die beiden Zusammenhangskomponenten, in welche der Baum B bei Entfernen einer der Kanten dieses Weges, deren Kantengewicht dem MinCut-Wert entspricht, zerfällt.

Ein kanonischer Strukturbaum benötigt dabei höchstens n-2 zusätzliche Knoten, wobei n die Anzahl der Knoten im Graphen G ist. Besitzt der Graph G Gelenkpunkte oder Brücken, so bleiben diese im Strukturbaum erhalten. Die Konstruktion eines kanonischen Strukturbaums in Polynomialzeit kann nicht alle möglichen s-t-MinCuts berücksichtigen, da es exponentiell viele von ihnen geben kann. Stattdessen könnte man als Grundlage für einen Algorithmus lediglich die kleinsten s-t-MinCuts für jedes Paar von Knoten heranziehen, da es von diesen nur polynomiell viele gibt und diese in polynomieller Zeit berechnet werden können.