From Egres Open
Jump to: navigation, search

A graft is a pair (G,T) where G=(V,E) is an undirected graph and [math]T \subseteq V[/math] is a node set of even cardinality. A T-join of the graft (G,T) is a subset [math]F \subseteq E[/math] of edges with the property that [math]d_F(v)[/math] is odd precisely if [math]v \in T[/math].

A subset X of nodes is T-odd if [math]|X \cap T|[/math] is odd. The cut [math]\delta(X)[/math] is called a T-cut if X is T-odd (clearly, X is T-odd if and only if V-X is T-odd). It is easy to see that the intersection of a T-join and a cut [math]\delta(X)[/math] is odd if and only if X is T-odd.

In bipartite graphs, the minimum cardinality of a T-join equals the maximum number of edge-disjoint T-cuts by a theorem of Seymour [1]. This is not true in general graphs, but the T-join polyhedron is always described by

[math]\{x \in {\mathbb R}^E: x \geq 0, \sum_{e \in C}x_e \geq 1 \text{ for every T-cut C}\}[/math]

by the results of Edmonds and Johnson [2]. They also showed that a minimum weight T-join can be found using the minimum weight perfect matching algorithm, for arbitrary weights. Padberg and Rao [3] proved that a minimum weight T-cut can be found using the Gomory-Hu tree of the graph.

For a survey, see Frank [4].


  1. P.D. Seymour, On odd cuts and plane multicommodity Flows, DOI link.
  2. J. Edmonds, E.L. Johnson, Matching, Euler tours and the Chinese postman problem, DOI link.
  3. M.W. Padberg, M.R. Rao, Odd minimum cut-sets and b-matchings, DOI link.
  4. A. Frank, A survey on T-joins, T-cuts, and conservative weightings, CiteSeer link, author link.