If $G$ is a loop-free undirected graph with at least one edge, prove that $G$ is bipartite if and only if $\chi(G)=2.$
Definition 11.18 A graph $G=(V,E)$ is called bipartite if $V=V_1 \cup V_2$ with $V_1 \cap V_2 = \emptyset$, and every edge of $G$ is of the form $\{a,b\}$ with $a\in V_1$ and $b\in V_2$.
I start by supposing $G$ is bipartite, coloring the vertices in $V_1$ $\color{blue}{blue}$ and the vertices in $V_2$ $\color{red}{red}$, then by definition of bipartite, every edge $\{a,b\}$ has vertices of different colors. $\chi(G)=2$.
Next, if $\chi(G)=2$, then if $\{a,b\}\in G$, then $a$ and $b$ are colored with different colors, and since $\chi(G)=2$ there are only two colors. There is no edge where both vertices are of the same color. You can write $V=V_1 \cup V_2$ where $V_1$ is all the vertices of color $1$, $V_2$ of color $2$. $V_1 \cap V_2 = \emptyset$ because no vertex is colored twice, and every edge is of the form $\{a,b\}$ where $a \in V_1$ and $b \in V_2$. Thus $G$ is bipartite.
Apparently I was supposed to make use of the fact that there was at least one edge?
Best Answer
If there are no edges, then we have the empty graph on $n$ vertices (which only requires one color) or the null graph (the graph on no vertices, which has chromatic number $0$).
A graph $G$ with at least one edge is bipartite iff $\chi(G) = 2$. In general, a graph $G$ is bipartite iff $\chi(G) \leq 2$.
Note that in the definition of a bipartite graph, there is no stipulation that $V_{1}, V_{2}$ are non-empty.