Complete Tripartite Graphs

*Definition:*

A *complete tripartite graph* G, designated
K_{m,n,r}, has the following properties.

1. The vertices can be partitioned into 3 subsets, M, N and R.

2. Each vertex is M is connected to all vertices in N and R.

Similarly for the vertices in N and R.

3. No vertex in M is connected to any other vertices in M.

Similarly for the vertices in N and R.

*Example:*

Graph G is the complete tripartite graph K_{3,3,3}.

The set M is comprised of the blue vertices, N of the red vertices, and R of

the yellow vertices.

Every blue vertex is connected to all the yellow and red ones.

Every red vertex is connected to all the yellow and blue ones.

Every yellow vertex is connected to all the blue and red ones.

*Definition:*

The* complete quadpartite graph* G,
designated K_{m,n,r,s}, is defined similarly. All vertices can be
partitioned into 4 subsets, with the vertices in each subset being connected to
those in the other subsets, but not to any vertices in the same subset. A
quadpartite graph is also designated as a *comlete 4-partite graph*.

The* complete quintpartite graph* G,
designated K_{m,n,r,s,t}, is defined similarly. All vertices can be
partitioned into 5 subsets, with the vertices in each subset being connected to
those in the other subsets, but not to any vertices in the same subset. A
quintpartite graph is also designated as a *complete 5-partite graph*.

Similarly, we can define complete *6-partite*
graphs, *7-paratite* graphs, etc.