2025/05/22 by Samuel Humeau, Humeau, Samuel, Damien Pous +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2505.16431
openalex publication_date 2025/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A tuple (s1,t1,s2,t2) of vertices in a simple undirected graph is 2-linked when there are two vertex-disjoint paths respectively from s1 to t1 and s2 to t2. A graph is 2-linked when all such tuples are 2-linked. We give a new and simple proof of the ``two paths theorem'', a characterisation of edge-maximal graphs which are not 2-linked as webs: particular near triangulations filled with cliques. Our proof works by generalising the theorem, replacing the four vertices above by an arbitrary tuple; it does not require major theorems such as Kuratowski's or Menger's theorems. Instead it follows an inductive characterisation of generalised webs via parallel composition, a graph operation consisting in taking a disjoint union before identifying some pairs of vertices. We use the insights provided by this proof to design a simple O(nm) recursive algorithm for the ``two vertex-disjoint paths'' problem. This algorithm is constructive in that it returns either two disjoint paths, or an embedding of the input graph into a web.