I have been struggling with the concept of T-Joins for an embarrassingly long time.
This is a definition from a text book:
Let G be a graph and let T be an even subset of V . A spanning subgraph H of G is called a T-join if $d_H(v)$ is odd for all v ∈ T and even for all v ∈ V \ T.
From Graph Theory by J.A. Bondy and U.S.R. Murty
Am I right in saying that this means that a T-Join is a graph which has all the same vertices of the original graph, but only the edges which ensure that all of the vertices in some set T have odd degree, and all the vertices which are not in T have even degree?
Questions:
Do all graphs have T-Joins for all different sets of T?
Can a graph have multiple T-Joins for the same T?
Are there other properties of T-joins I should think about?
Why are T-Joins so important?
Thank you very much for your time
No. In fact, an immediate consequence of the handshaking lemma, there is no T-join with |T| odd. On the other hand, if the vertices T lie in the same component and |T| is even, then there exists a T-join.
Yes. If you have a T-join and add/remove a cycle to/from it, you still have a T-join, since every vertex in the join will have the same parity.
This is a useful characterization: $H$ is a T-join if and only if $H$ can be partitioned into edge-disjoint cycles and paths such that the |T|/2 paths connect disjoint vertices in T.
Thus you may think about the set of $\emptyset$-joins being the set of all Eulerian subgraphs. If $T=\{s,t\}$, then T-joins are $st$-paths plus some number of edge-disjoint cycles.
From a computational perspective, T-joins generalize many natural graph problems and can still be computed efficiently. For example, determining if there is a path between two nodes $s$ and $t$ is equivalent to determining if there is an $\{s,t\}$-join. Moreover, one can efficiently optimize over T-joins; given a weight function $w$ on the edges, there is a polynomial-time algorithm to find a minimum-cost T-join with respect to $w$.
The Chinese Postman Problem is a famous non-trivial problem that can be easily cast as a minimum-cost T-join problem. The goal is to find the shortest tour of an undirected graph $G = (V, E)$ that visits every edge at least once and returns to the starting vertex. Although superficially similar to the Traveling Salesman Problem, the Chinsese Postman Problem can be solved in polynomial time as follows. Let $T$ be the set of vertices of odd degree and set $w(e) = 1$ for all edges $e$. Now compute a minimum-cost $T$-join $J$ with respect to $w$, and form the multigraph $G'$ by duplicating the edges in $J$. An Eulerian cycle in $G'$ now corresponds to the desired Chinese Postman tour in $G$.