Combinatorics • Topic 31

Bipartite Graphs

Bipartite graphs model relationships between two different types of objects (e.g., Students and Classes).

Definition

Definition (Bipartite Graph)

A graph

G = (V, E)

is bipartite if

V

can be partitioned into two sets

X

and

Y

such that every edge connects a vertex in

X

to one in

Y

Theorem

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

All edges between a set of size

m

and a set of size

n

exist.

Exercise (Problem 1)

Prove that all trees are bipartite.

Exercise (Problem 2)

Is the cycle graph

C_{6}

bipartite? What about

C_{5}

Exercise (Problem 3)

What is the maximum number of edges in a bipartite graph with

n

vertices? (Turán's Theorem case).