Applying Hall's Theorem to a tripartite graph

172 Views Asked by At

Hall's theorem works for bipartite graphs and shows there is a complete matching if Hall's condition holds. If I have a tripartite graph $(X,Y,Z,E)$ and Hall's condition holds from $X$ to $Y$ , from $X$ to $Z$ and from $Y$ to $Z$. Would this be a satisfactory condition to find a complete matching of "triangles" on $X$?

1

There are 1 best solutions below

0
On

No it is not strong enough. Suppose $G$ is a cycle on $3n$ vertices; $n$ an integer satisfying $n \ge 2$ i.e., $V(G)= \mathbb{Z}/3n\mathbb{Z}$, and $i$ and $j$ are adjacent iff $i-j \equiv_3 1$. Then $G$ is tripartite w sides $X_0,X_1,X_2$; $X_i =\{j; j \equiv_3 i\}$. Can you see the rest from here.