Bipartite Graph
This is a more specific case of Graph Colouring with two colors.
A graph is bipartite if and only if it is two-colorable.
Odd cycle
A graph is bipartite exactly when it does not contain a cycle with an odd number of edge
int n;
vector<vector<int>> adj; // Undirected Graph
vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
if (side[st] == -1) {
q.push(st);
side[st] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (side[u] == -1) {
side[u] = side[v] ^ 1;
q.push(u);
} else {
is_bipartite &= side[u] != side[v];
}
}
}
}
}
cout << (is_bipartite ? "YES" : "NO") << endl;
MATH239
Bipartite Graph
A graph is bipartite if its vertex set can be partitioned into two disjoint sets , such that and every edge in has one endpoint in and one endpoint in .
Complete Bipartite Graph
For positive integers , , the complete bipartite graph is the graph with bipartition , where and , containing all possible edges joining vertices in with vertices in .
Notice that there are edges in
Theorems
Theorem 5.3.2
A graph is bipartite it has no odd cycles.
How to Prove a Graph is Bipartite?
Create a bipartition, and show how the edges have one end in both sets.
- Proof done using Connectedness: