**Bipartite graphs and partitions**

In a *bipartite graph,* it is possible to partition the set of vertices into two sets such that none of the vertices in either set are adjacent to one another.

Here are some examples: |

An *n-partite graph* is defined similarly, with the vertices partitioned into* n* sets
or partitions.

A *complete n-partite* graph is a graph where every vertex in each partition is connected to
all the vertices of the graph which are not contained in that partition A complete *n*-
partite graph is denoted *K*(*p*_{1}, *p*_{2}, . . . , *p*_{n})
where *p*_{n} denotes the number
of vertices in each partition. Thus *K*(3, 3) is a complete bipartite graph with 3 vertices in each partition and *K*(3, 4, 5) is a complete tripartite graph with partitions of 3, 4, and 5 vertices.

K(3, 3) |
K(4, 2) |
K(2, 3, 2) |

Copyright © 1999-2000 SciMathMN