Definition (Bipartite Graph)

A bipartite graph is a Graph that partitions a left and right side. Indeed, .

  • .
  • All edges connect a vertex in to a vertex in .
graph
    L1((L1)) o--o R2((R2))
    L1 o--o R3((R3))
    L2((L2)) o--o R1((R1))
    L2 o--o R2
    L2 o--o R3
    L3((L3)) o--o R1
    L3 o--o R2
    L3 o--o R3

Formal

We want a way to define a bipartite graph without having to rearrange the vertices when drawing them. In particular, we want to (further) formalize the definition.

A graph is bipartite if we can color vertices white and black such that each edge connects a white vertex to a black vertex.

Definition (Complete Bipartite Graph)

Denoted as a complete bipartite graph denotes a graph where and . Every vertex on the left has an edge to the right side and vice versa.

graph
    L1((L1)) o--o R1((R1))
    L1 o--o R2((R2))
    L1 o--o R3((R3))
    L1 o--o R4((R4))
    L1 o--o R5((R5))
    L2((L2)) o--o R1
    L2 o--o R2
    L2 o--o R3
    L2 o--o R4
    L2 o--o R5

The Degree of is equal to .

Theorem (Bipartite Cycles)

Graph is bipartite iff it contains no odd length Cycle.

Proof: See Theorem (Bipartite Cycles).