How to tell if a graph is bipartite?
Sebastian Wright 
So
I have the following graphs drawn. How can I tell whether they are bipartite? If it is bipartite, how to identify 2 disjoint non empty sets?
$\endgroup$ 13 Answers
$\begingroup$Use the vertex colouring algorithm:
1) Colour any one of your vertices red.
2) Identify all uncoloured vertices that are adjacent to a red vertex. Colour them blue.
3) Identify all uncoloured vertices that are adjacent to a blue vertex. Colour them red.
4) Repeat steps 2 and 3 until all the vertices are coloured red or blue.
5) If there are any two vertices adjacent of the same colour, then your graph is not bipartite, otherwise it is bipartite.
6) If the graph is bipartite, the colouring algorithm will have created the two required sets of points (one red and one blue).
$\endgroup$ $\begingroup$A quick way to see that the graph (b) can't possibly be bipartite is to notice it has a triangle. Why is this a problem? Well, bipartite graphs are precisely the class of graphs that are 2-colorable. Recall a coloring is an assignment of colors to the vertices of the graph such that no two adjacent vertices receive the same color. So if you can 2-color your graph, it will be bipartite. Clearly, if you have a triangle, you need 3 colors to color it.
When you have a 2-coloring, the two color classes (red vertices, blue vertices), give you the bipartization.
$\endgroup$ $\begingroup$A graph is bipartite if and only if there does not exist an odd cycle within the graph. Suppose the graph in b) is bipartite, i.e. there exists two disjoint non-empty sets $A$ and $B$. Consider the cycle $v_2,v_4,v_5$. Let $v_2$ be in $A$. Since $v_2$ is adjacent to $v_4$, $v_4$ must be in $B$. But $v_5$ is adjacent to both $v_2$ and $v_4$, therefore it cannot be in either $A$ or $B$. Therefore the graph is not bipartite.
$\endgroup$
