# The two disjoint rooted paths problem

*Discrete Structures and Algorithms (Reading Group): Graph Minors*

*by Gwena\"el Joret*

*Institution:*Universit\'e Libre de Bruxelles

*Date: Mon 26th September 2011*

*Time: 11:00 AM*

*Location: Room 107, Richard Berry Building*

*Abstract*: Given four distinct vertices $s_1, s_2, t_1, t_2$ of a graph $G$, Menger's theorem tells us exactly when there exist two vertex-disjoint paths in $G$ between $\{s_1, s_2\}$ and $\{t_1, t_2\}$: the obvious necessary condition is sufficient. But what if we moreover require that these two paths link $s_1$ to $t_1$ and $s_2$ to $t_2$? Here the answer is less straightforward, the paths exist if and only if a certain auxiliary graph contains a special kind of $K_5$ minor. I will present this result and its proof at the next meeting.