Bipartite graphs

#matematik-discmath

Definition: Bipartite graph

A graph is bipartite if , where is the Chromatic number of .

Theorem

A graph is bipartite if and only if it contains no cycles with odd length.

Given any Relation between disjoint sets and , we can create a bipartite graph describing the relation, by taking and letting . Clearly it's bipartite, since we can simply color all of with the first color, and all of with the second.

Theorem

Let be a bipartite graph and let be the degree of in . Then Proof:
We get and likewise for .