A shorter proof of the graph minor algorithm: the unique linkage theorem

At the core of the seminal Graph Minor Theory of Robert-son and Seymour is a powerful theorem which describes the structure of graphs excluding a fixed minor. This result is used to prove Wagner’s conjecture and provide a polyno-mial time algorithm for the disjoint paths problem when the number of the terminals is fixed (i.e, the Graph Minor Algorithm). However, both results require the full power of the Graph Minor Theory, i.e, the structure theorem. In this paper, we show that this is not true in the latter case. Namely, we provide a new and much simpler proof of the correctness of the Graph Minor Algorithm. Specifi-cally, we prove the“Unique Linkage Theorem”without using Graph Minors structure theorem. The new argument, in ad-dition to being simpler, is much shorter, cutting the proof by at least 200 pages. We also give a new full proof of correct-ness of an algorithm for the well-known edge-disjoint paths problem when the number of the terminals is fixed, which is at most 25 pages long. Categories and Subject Descriptor