Solution
= Solution
This is false. For a central integer $s$, let
$$
A=\{x\in[k]^3:x_1+x_2+x_3<s\},
\qquad
B=\{x\in[k]^3:x_1+x_2+x_3>s\}.
$$
They are disjoint and no edge joins them; the omitted central layer has only $(3/4+o(1))k^2$ points. By choosing the central $s$ symmetrically, both sides have
$$
\frac12\big(k^3-(3/4+o(1))k^2\big)
>\frac{k^3-k^2}{2}
$$
for large $k$.