2

An $r$-regular expander should do it. The following is a simple observation that I first saw in Li (arXiv:2106.05513): if an $r$-regular graph has conductance $\phi$, then the smaller side $S$ of a minimum cut contains at most $|S| \leq 1/\phi$ vertices. Indeed, by definition of conductance we have that $|E(S,S^c)| \geq \phi r |S|$. Since this defines a ...


1

How about the following counter-example? $m=2$, $n=4$. $A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$. $T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$. With the partition $A\cup B\cup C = \{a_1,b_1\}\cup\{a_2,b_2\}\cup\{c_1\}\cup\{c_2\}$.


Only top voted, non community-wiki answers of a minimum length are eligible