A linkage L in a graph G is a subgraph each component of which is a path, and it is vital if V (L) = V (G) and there is no other linkage in G joining the same pairs of vertices. We show that, if G has a vital linkage with p components, then G has tree-width bounded above by a function of p. This is the major step in the proof of the unproved lemma from Graph Minors XIII, and it has a number of other applications, including a constructive proof of the intertwining conjecture.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Disjoint paths
- Graph minors
- Intertwining conjecture