Thomassen's theorem on the two-linkage problem in acyclic digraphs: A shorter proof

Paul Seymour

doi:10.1016/j.jctb.2025.08.006

Thomassen's theorem on the two-linkage problem in acyclic digraphs: A shorter proof

Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let G be an acyclic digraph, and let a,b,c,d∈V(G), where a,b are sources, c,d are sinks, and every other vertex has in-degree and out-degree at least two. In 1985, Thomassen showed that there do not exist disjoint directed paths from a to c and from b to d, if and only if G can be drawn in a closed disc with a,b,c,d drawn in the boundary in order. We give a shorter proof.

Original language	English (US)
Pages (from-to)	97-100
Number of pages	4
Journal	Journal of Combinatorial Theory. Series B
Volume	176
DOIs	https://doi.org/10.1016/j.jctb.2025.08.006
State	Published - Jan 2026

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Acyclic digraphs
Disjoint paths
Planarity

Access to Document

10.1016/j.jctb.2025.08.006

Cite this

@article{99f16ba2693e4da5b6f485c0f65b5ad9,

title = "Thomassen's theorem on the two-linkage problem in acyclic digraphs: A shorter proof",

abstract = "Let G be an acyclic digraph, and let a,b,c,d∈V(G), where a,b are sources, c,d are sinks, and every other vertex has in-degree and out-degree at least two. In 1985, Thomassen showed that there do not exist disjoint directed paths from a to c and from b to d, if and only if G can be drawn in a closed disc with a,b,c,d drawn in the boundary in order. We give a shorter proof.",

keywords = "Acyclic digraphs, Disjoint paths, Planarity",

author = "Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier Inc.",

year = "2026",

month = jan,

doi = "10.1016/j.jctb.2025.08.006",

language = "English (US)",

volume = "176",

pages = "97--100",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Thomassen's theorem on the two-linkage problem in acyclic digraphs

T2 - A shorter proof

AU - Seymour, Paul

PY - 2026/1

Y1 - 2026/1

N2 - Let G be an acyclic digraph, and let a,b,c,d∈V(G), where a,b are sources, c,d are sinks, and every other vertex has in-degree and out-degree at least two. In 1985, Thomassen showed that there do not exist disjoint directed paths from a to c and from b to d, if and only if G can be drawn in a closed disc with a,b,c,d drawn in the boundary in order. We give a shorter proof.

AB - Let G be an acyclic digraph, and let a,b,c,d∈V(G), where a,b are sources, c,d are sinks, and every other vertex has in-degree and out-degree at least two. In 1985, Thomassen showed that there do not exist disjoint directed paths from a to c and from b to d, if and only if G can be drawn in a closed disc with a,b,c,d drawn in the boundary in order. We give a shorter proof.

KW - Acyclic digraphs

KW - Disjoint paths

KW - Planarity

UR - https://www.scopus.com/pages/publications/105015429124

UR - https://www.scopus.com/inward/citedby.url?scp=105015429124&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2025.08.006

DO - 10.1016/j.jctb.2025.08.006

M3 - Article

AN - SCOPUS:105015429124

SN - 0095-8956

VL - 176

SP - 97

EP - 100

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Thomassen's theorem on the two-linkage problem in acyclic digraphs: A shorter proof

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this