KöMaL 2024 B5397

Let $G$ be a graph (possibly with multiple edges) with the following property: whenever the vertices of $G$ are partitioned into $t$ disjoint sets, there are at least $2t-2$ edges connecting different sets. Show that the edges of $G$ can be colored red or blue such that the red edges and the blue edges each form a connected graph (and reaching all the vertices).