Complete Tripartite Graphs

Definition:

A complete tripartite graph G, designated Km,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 K3,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. 

 

G

 

Definition:

The complete quadpartite graph G, designated Km,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 Km,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.