About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp

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:bipartite graph bipartite graph
In a tripartite graph, the vertices are partitioned into three sets (partitions) so that no two vertices contained in any one partition are adjacent.

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(p1, p2, . . . , pn) where pn 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)
K(3, 3) K(4, 2) K(2, 3, 2)

Copyright © 1999-2000 SciMathMN