Bipartite graphsA simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint nonempty sets V_{1} and V_{2} such that every edge in the graph connects a vertex in V_{1} and a vertex in V_{2} (so that no edge in G connects either two vertices in V_{1} or two vertices in V_{2}).
Example. C_{6} is bipartite since its vertex set can be partitioned into the two sets and , and every edge of C_{6} connects a vertex in V_{1} and a vertex in V_{2}.
Example. K_{3} is not bipartite. To see this, note that if we divide the vertex set of K_{3} into two disjoint sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices could not be connected by an edge, but in K_{3} each vertex is connected to every other vertex by an edge.
Example. Are the graphs G and H bipartite?
Solution: Graph G is bipartite, since its vertex set is the union of two disjoint sets {a, b, d} and {c, e, f, g}, and each edge connects a vertex in one of these subsets to a vertex in the other subset. Note that for G to be bipartite it is not necessary that every vertex in {a, b, d} be adjacent to every vertex in {c, e, f, g}. For instance, b and g are not adjacent.
Graph H is not bipartite since its vertex set cannot be partitioned into two subsets so that edges do not connect two vertices from the same subset.
Example. The complete bipartite graph is the graph that has its vertex set partitioned into two subsets of m and n vertices, respectively. There is an edge between two vertices iff one vertex is in the first subset and the other vertex is in the second subset.
Date: 20150102; view: 1026
