---
tag: Z181SK9269
kind: concept
name: Bipartite
sources:
  - wikipedia: en:325802@r1373839425
    locator: Glossary of graph theory, section B
    note: adopted
    mention: wikipedia://en/325802#XVKF
    sections: [Summary]
inventory: [KJ7SDP35WC]
---

## Summary

A [[bipartite graph|07DVHJ8N0A]] is a graph whose vertices can be divided into two disjoint sets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another way, a bipartite graph is a graph with no odd cycles; equivalently, it is a graph that may be properly colored with two colors. Bipartite graphs are often written $G = (U,V,E)$ where $U$ and $V$ are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.