# T-join

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]}.

## References

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