One of the major results in graph theory is the graph structure theorem from Robertson and Seymour
<https://en.wikipedia.org/wiki/Graph_structure_theorem>. It gives a deep and fundamental connection between the theory of graph minors and topological embeddings, and is frequently applied for algorithms.


I was working with this results for years, and now heard someone saying that Robertson and Seymour called this result a "red herring". Is this true, and why would they possibly call such a breakthrough result a red herring?


(Edit: my question refers to the 2003 graph structure theorem, not to the graph minor theorem which they established later)



Why did Robertson and Seymour call their breakthrough result a "red herring"?
Seymour and Robertson have indeed said that, and in fact they wrote that in their 2003 article in which they published the graph structure theorem.


Here is the quote from Robertson and Seymour „Graph Minors. XVI. Excluding a non-planar graph“ (Journal of Combinatorial Theory, Series B, Vol. 89, Issue 1, Sept. 2003, pages 43–76, doi:[10.1016/S0095-8956(03)00042-X](https://doi.org/10.1016/S0095-8956%2803%2900042-X)).
Their **theorem 1.3** is the earliest version of what we now call the graph structure theorem.



> 
> While 1.3 has been one of the main goals of this series of papers, it turns out to have been a red herring. There is another result (theorem 3.1) which is proved in this paper, and from which 1.3 is then derived; and in all the future applications in this series of papers, it is not 1.3 but 3.1 that will be needed.
> 
> 
> 


My reading is, they were calling it a red herring because, at this point, they realized the importance of the concept of a *tangle*. (I think Reinhard Diestel said that the notion of a tangle is perhaps the deepest single innovation for graph theory stemming from this proof.)


Continuing the quote of Robertson and Seymour (the bold font is from me, not from the article):



> 
> Let us explain how theorem 3.1 is used to prove 1.3. Evidently we would like to eliminate the ‘‘tree-structure’’ part of 1.3 and concentrate on the internal structure of one of the ‘‘nodes’’ of the tree. How can we do so? An inductive argument looks plausible at first sight; if there is no low order cutset of G dividing it into two substantial pieces then G itself must be almost a ‘‘node’’ if the theorem is to be true, while if there is such a cutset we may express G as a clique-sum of two smaller graphs, and hope to apply our inductive hypothesis to these graphs. But there is a difficulty here; it is possible that these smaller graphs have an L-minor while G does not. Fortunately there is a way to focus in on a ‘‘node’’ which does not involve any decomposing, as follows. We can assume that the tree is as refined as possible in the sense that no node can be split into two smaller nodes, and so for every low order cutset of G; most of any node will lie on one side or the other of the cutset (except for nodes of bounded cardinality, which we can ignore.) Therefore if we fix some node, every small cutset has a ‘‘big’’ side (containing most of the node) and a ‘‘small’’ side—and it turns out that no three small sides have union G: Thus a node defines a **‘‘tangle’’**, which is such an assignment of big and small sides to the low order cutsets; and conversely, it can be shown that any **tangle** in G of sufficiently high ‘‘order’’ will be associated with some node of the tree-structure. Hence a convenient way to analyze the internal structure of the nodes is to analyze the local structure of G with respect to some high order **tangle**, and this is the content of theorem 3.1.
> 
> 
> 


