Why did Robertson and Seymour call their breakthrough result a "red herring"?

Question

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)

Answer 1

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). 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.

Answer 2

If you are interested in tangles in the sense of Robertson and Seymour, this is just to provide some perspective on it. I am working on this for my Ph.D. project and I thought maybe it is considered helpful if I share this high-level, intuitive perspective here (it is not a detailed definition):

The best and shortest description, I think, is given in the following quote. It mentions the proof of the graph minor theorem, but in fact it is the same concept of tangles as in the proof of the graph structure theorem:

Quote: „Originally devised by Robertson and Seymour as a technical device for their proof of the graph minor theorem, tangles have turned out to be much more fundamental than this: they define a new paradigm for identifying highly connected parts in a graph.

Unlike earlier attempts at defining such substructures—in terms of, say, highly connected subgraphs, minors, or topological minors—tangles do not attempt to pin down this substructure in terms of vertices, edges, or connecting paths, but seek to capture it indirectly by orienting all the low-order separations of the graph towards it.

In short, we no longer ask what exactly the highly connected region is, but only where it is. For many applications, this is exactly what matters.

Moreover, this more abstract notion of high local connectivity can easily be transported to contexts outside graph theory. This, in turn, makes graph minor theory applicable beyond graph theory itself in a new way, via tangles.“ End of Quote.

This quote is from Reinhard Diestel, in the preface to the 5th edition of his Graph Theory book.