A quick proof of Seymour's theorem on t-joins (Q1089008)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A quick proof of Seymour's theorem on t-joins |
scientific article |
Statements
A quick proof of Seymour's theorem on t-joins (English)
0 references
1987
0 references
Let G be a graph and t: V(G)\(\to \{0,1\}\) where t(V(G)) is even. (If \(X\subseteq V(G)\), then \(t(X):=\Sigma \{t(x):\) \(x\not\in X\}.)\) A t-join is a set \(F\subseteq E(G)\) with \(d_ F(x)\equiv t(x)\) (mod 2), \(\forall x\in V(G)\). \((d_ F(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. If \(X\subseteq V(G)\), let \(\delta (X)=\{xy\in E(G):\) \(y\not\in X\), \(x\in X\}\). If t(X)\(\equiv 1(mod 2)\), then \(\delta\) (X) is called a t-cut. t-cuts contain plane multicommodity flows as a special case. \textit{P. O. Seymour} [Proc. Lond. Math. Soc., III. Ser. 42, 178-192 (1981; Zbl 0447.90026)] proved that if G is bipartite then \(\tau (G,t)=\nu (G,t)\). The author gives a short proof of this.
0 references
t-join
0 references
Chinese postman tours
0 references
matchings
0 references
minimum weight paths
0 references
t-cuts
0 references
plane multicommodity flows
0 references
0 references