Bipartite graphs

A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint nonempty sets V ₁ and V ₂ such that every edge in the graph connects a vertex in V ₁ and a vertex in V ₂ (so that no edge in G connects either two vertices in V ₁ or two vertices in V ₂).

Example. C ₆ is bipartite since its vertex set can be partitioned into the two sets and , and every edge of C ₆ connects a vertex in V ₁ and a vertex in V ₂.

Example. K ₃ is not bipartite. To see this, note that if we divide the vertex set of K ₃ 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 ₃ 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.

Дата добавления: 2014-12-23