Graph theory seminar - Alan Arroyo Guevara

The 2-Linkage Problem

Abstract:

Given a graph G and four vertices x1, x2, y1, y2, a 2-linkage is a pair of vertex disjoint paths, one connecting x1 to y1 and the other connecting x2 to y2. Jung showed that a 4-connected graph G has no 2-linkage if, and only if, it is planar and x1, x2, y1, y2 occur in this cyclic order on the boundary walk of some face. A few years later, Seymour and Thomassen generalized this result and characterized when a 2-linkage exists for a general graph. In this talk, we present and prove a generalization of Jung's theorem and discuss why planarity plays an important role in determining when a 2-linkage exists.