That $K_n$ is given, is a bit of a red herring. Replace it by a triangulation $G$ of the $n$ given points. The statement is trivial when all edges are labelled $0$, or all are labelled $1$. So without loss of generality, there is a vertex $x$ incident to a $0$-edge and a $1$-edge. By induction, $G-x$ has a spanning tree with all edges labelled the same, say with label $0$. Put $x$ back together with any $0$-edge incident to it, to obtain a spanning tree of the original set of points with all edges labelled $0$.
And of course the base case $n\leq 3$ is trivial.