Prove graph is bipartite

Question

How can I prove that a graph $G = (V, E)$ is bipartite if and only if $G$ can be coloured with $2$ colors/colours? I know it's true, but don't know how to do it other than drawing every possible graph.

Answer 1

Hint: If you have a $2$-coloring, let $G_{V_0}$ be the set of vertices of one color, and let $G_{V_1}$ be the set of vertices of the other color. Ask yourself the following question: Are there any edges between $G_{V_0}$ and $G_{V_1}$? (If not, you have a bipartite graph with vertex sets $G_{V_0}$ and $G_{V_1}$.)

Answer 2

Given a two-coloring, getting $G$ is bipartite should be easy. Just apply the definition of what it means to be a bipartite graph.

Now given $G$ is bipartite, I would approach this using proof by contradiction. Suppose $G$ isn't two-colorable. Let $x \in X$ and $y \in Y$ be adjacent vertices in distinct partitions such that there is a third vertex $z$ adjacent to both $x$ and $y$. Since $G$ is bipartite, where must $z$ belong? It can only belong in partitions $X$ or $Y$. You get a contradiction here.