Bipartite graph
Definition
Let be a graph with vertex set . Then is bipartite if is the union of two disjoint sets and with this property. Each edge of has one end in and one end in . The pair is a bipartition of .
Remarks
Equivalently, is bipartite if it has a proper colouring with colours. The complete bipartite graphs, the even cycle graphs and all trees are bipartite. A graph is bipartite if and only if it has no cycle of odd length. The node a graph is bipartite iff it has no odd cycle states this.
Where this leads
5 pages build on this one.
Further reading
- Web https://en.wikipedia.org/wiki/Bipartite_graph, lead section
About this page
| Tag | 07DVHJ8N0A |
|---|---|
| URI | m2://07DVHJ8N0A |
| Kind | definition |
| Writing | W1 stated |
| MSC | 05C75 |
| Defines | Bipartite graph |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.