Definition (Minimum T-Transversal): Let $T$ be the set of all triangles in a simple graph $G=(V,E)$. A T-transversal is a subset $S\subseteq E(G)$ such that every triangle in $T$ contains at least one edge from $S$. If $|S|\leq|\tilde{S}|$ for all T-transversals $\tilde{S}$, then $S$ is a minimum T-transversal and we denote $|S|=\tau_{\triangle}(G)$.
Definition (Maximum Packing): Let $T$ be the set of all triangles in a simple graph $G=(V,E)$. A packing is a subset $P\subseteq T$ such that all triangles in $P$ are pairwise edge-disjoint. If $|P|\geq|\tilde{P}|$ for all packings $\tilde{P}$, then $P$ is a maximum packing and we denote $|P|=\nu_{\triangle}(G)$.
Theorem 1: The maximum flow in a directed, unit-capacity graph is of value $n$ if and only if there exist $n$ pairwise edge-disjoint paths from $s$ to $t$.
Let $G=(A+B+C,E)$ be a tripartite graph such that, \begin{align*} |A|&=i, & |B|&=j, & |C|&=k, \end{align*} $i\leq j\leq k$, and the induced bipartite graph $G[A\cup B]$ is isomorphic to $K_{i,j}$.
I want to find a packing of size $\tau_{\triangle}(G)$ in $G$. To do this, I consider the subgraph $H=G\setminus E_{AB}$ where $E_{AB}$ denotes the set of edges between $A$ and $B$. If I can find $\tau_{\triangle}(G)$ pairwise edge-disjoint paths from $B$ to $A$ in $H$ such that any two paths have, at most, one common vertex, I can form a packing by joining both ends of each path to unique vertex in $A$ (I can do this because $G[A\cup B]\cong K_{i,j}$).
Let $\tau_{\triangle}(G)=n$. To find $n$ pairwise edge-disjoint paths from $B$ to $A$ in $H$, I create a network from $H$ in order to apply Theorem 1. I create $2n$ new vertices and join all the vertices in $B$ to $n$ of these new vertices, and join all the vertices in $A$ to the other $n$ new vertices. I then add a source joined to the $n$ vertices adjacent to $B$ and add a sink joined to the $n$ vertices adjacent to $A$. Lastly, I give all edges in this network capacity 1. So I end up with a network like the one below:
Note that the edges between $A$ (magenta), $B$ (cyan), and $C$ (yellow) are dotted to emphasize these are arbitrary edges. Then, by Theorem 1, supposing the maximum flow in this network is $n\implies$ there are $n$ pairwise edge-disjoint $s$ to $t$ paths in the network $\implies$ there are $n$ pairwise edge-disjoint $B$ to $A$ paths in $H$.
Recall, however, that I need the paths from $B$ to $A$ to also have the property that any two paths share at most one vertex. Is there a way to implement this additional constraint into this network flow model? Does this additional constraint on the paths bar me from using network theory? Any help would be greatly appreciated!
