bipartite graph

A bipartite graph is a graph with a chromatic number of $2$ .

The following graph, for example, is bipartite:

\\xymatrix{{\\color[rgb]{1,0,0}A}\\ar@{-}[rrr]\\ar@{-}[rd]\\ar@{-}[ddd]&&&{\\color[%rgb]{0,0,1}B}\\\\&{\\color[rgb]{0,0,1}E}&{\\color[rgb]{1,0,0}F}\\ar@{-}[ur]\\ar@{-}[l]\\ar@{-}[d]&\\\\&{\\color[rgb]{1,0,0}H}\\ar@{-}[u]\\ar@{-}[r]\\ar@{-}[dl]&{\\color[rgb]{0,0,1}G}&\\\\{\\color[rgb]{0,0,1}D}&&&{\\color[rgb]{1,0,0}C}\\ar@{-}[uuu]\\ar@{-}[lll]\\ar@{-}[%ul]}

One way to think of a bipartite graph is by partitioning the vertices into two disjoint sets where vertices in one set are adjacent only to vertices in the other set. In the above graph, this may be more obvious with a different :

\\xymatrix{{\\color[rgb]{1,0,0}A}\\ar@{-}[r]\\ar@{-}[rd]\\ar@{-}[rdd]&{\\color[rgb]{%0,0,1}E}\\\\{\\color[rgb]{1,0,0}F}\\ar@{-}[ru]\\ar@{-}[r]\\ar@{-}[rdd]&{\\color[rgb]{0,0,1}B}\\\\{\\color[rgb]{1,0,0}H}\\ar@{-}[ruu]\\ar@{-}[r]\\ar@{-}[rd]&{\\color[rgb]{0,0,1}D}\\\\{\\color[rgb]{1,0,0}C}\\ar@{-}[ruu]\\ar@{-}[ru]\\ar@{-}[r]&{\\color[rgb]{0,0,1}G}}

The two subsets are the two columns of vertices, all of which have the same colour.

A graph is bipartite if and only if all its cycles have even length. This is easy to see intuitively: any path of odd length on a bipartite must end on a vertex of the opposite colour from the beginning vertex and hence cannot be a cycle.