A graph $G$ is bipartite if and only if $G$ can be coloured with 2 colours I've been stuck on this question for some time, can anyone please help me out with it... Definition: A graph $G = (V, E)$ can be coloured with $k$ colours if $\forall v \in V$, $v$ is assigned exactly one of $k$ colours and $\forall e = (u, v) \in E$, $u$ and $v$ are coloured with different colours. Prove that a graph $G = (V, E)$ is bipartite if and only if $G$ can be coloured with 2 colours.

Big HINT: If you have a $2$-coloring, let $V_0$ be the set of vertices of one color, and let $V_1$ be the set of vertices of the other color. Are there any edges between two vertices in $V_0$ or between two vertices of $V_1$? If not, you have a bipartite graph with vertex sets $V_0$ and $V_1$.

On the other hand, if $G$ is bipartite with vertex sets $V_0$ and $V_1$, what happens if you color every vertex in $V_0$ one color and every vertex in $V_1$ another color?