As a part of my thesis I have to consider undirected simple bipartite graphs $G = (U, V, E)$ whose edges can be colored with two colors 0 and 1.
Such a coloring $\gamma : E \rightarrow \{0,1\}$ of $G$ is separating if we have that for every $u,u' \in U, u \neq u'$, they are connected by an at least one alteratingly colored path of length exactly two: That is, the vertex $v \in V$ between them separates $u$ and $u'$ by having differently colored edges to them. For other paths between $u$ and $u'$, the length and the coloring can be arbitrary.
I have to prove: If $G$ has a separating edge coloring, then $G$ contains the complete graph of $\log |U|$ vertices as a minor, where $\log = \log_2$ denotes the binary logarithm.
I managed to show that $|V| \geq \log |U|$ and $|E| \geq |U| \cdot \log |U|$ are necessary properties (which can be shown by interpreting a coloring as a biclique covering of $K_{|U|}$), and there are infinitely many graphs for which the bounds are exact.
Also, the cases where $|V|$ is minimal/maximal are clear, that is $G$ being a complete bipartite graph or a pseudo-clique (every $u,u'$ pair is separated by a new $V$-vertex of degree 2).
But besides that, I have to admit that I am completely lost here (it's my first serious graph theoretic problem).