A quick proof of Seymour's theorem on t-joins

✍ Scribed by András Sebö

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 163 KB
• Volume: 64
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90246-9

✦ Synopsis

A very short proof of Seymour's theorem, stating that in bipartite graphs the minimum cardinality of a t-join is equal to the maximum cardinality of an edge-disjoint packing of t-cuts, is given.

Let G be a graph and t:V(G)-, {0, 1}, where t(V(G)) is even. (If X~_ V(G), then t(X):=E {t(x):xeX}.) A t-join is a set F~E(G) with d~(x)=t(x) (mod 2), Vx e V(G). (dF(x) denotes the number of edges of F incident with x, where loops count twice.) t-joins contain Chinese postman tours, matchings and minimum weight paths as a special case. (el. ).

If Xc V(G), let 6(X)= {xy e E(G): y qX, x eX}. If t(X)~ 1 (mod 2), then 6(X) is called a t-cut, t-cuts contain plane multicommodity flows as a special case . For basic definitions concerning graphs we refer to .