The topic of this post is bipartite graphs. These are graphs whose vertex set can be partitioned into two parts, called partite sets, such that all edges of the graph are such that and are in different partite sets. The most common examples of bipartite graphs are the trees and even cycles. Any union of bipartite graphs obviously yields another bipartite graph. The complete bipartite graph consists of two partite sets and containing and elements respectively with all possible edges between and filled out.
To conclude here is a list of characterizations.
Suppose is a graph with at least two vertices. The following are equivalent:
1. is bipartite.
2. Every cycle of is even.
: Suppose is bipartite and there is a cycle which has an odd number of edges. Now for odd is in the same partite set as . But since the cycle is odd and are in the same partite set which is a contradiction.
Conversely suppose has no odd cycles and . Let is even and is odd . Then and partition . Suppose and . Neither nor is for otherwise (resp ) is odd. So it makes sense to talk of a path from to (resp ). Let and be the shortest such paths. (Note that they are necessarily even). Let the last common vertex in the two paths be . Now the cycle is an odd cycle. This contradiction proves there are no edges within vertices of . Similarly there are no edges within vertices of . The result follows.
: This is more of a restatement of the definition of a bipartite graph then a characterization, since the two partite sets may be considered as differently colored subsets of .
In addition to the above general characterizations the following are also true:
a) G is bipartite iff the spectrum of is symmetric with respect to the origin.
b) Suppose is connected and is its maximum eigenvalue. Then is bipartite iff is an eigenvalue of .
c) Suppose is planar. Then is bipartite iff , the bound degree of a region , is even for every region .
I will defer a proof of these statements.