Question

The complete m-partite graph \({{\rm{K}}_{{{\rm{n}}_{\rm{1}}}{\rm{,}}{{\rm{n}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{n}}_{\rm{m}}}}}\)has vertices partitioned into \({\rm{m}}\)subsets of \({{\rm{n}}_{\rm{1}}}{\rm{,}}{{\rm{n}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{n}}_{\rm{m}}}\)elements each, and vertices are adjacent if and only if they are in different subsets in the partition.

How many vertices and how many edges does the complete m-partite graph \({{\rm{K}}_{{{\rm{n}}_{\rm{1}}}{\rm{,}}{{\rm{n}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{n}}_{\rm{m}}}}}\)have?

Short answer

The number of vertices \(\sum\limits_{{\rm{i = 1}}}^{\rm{m}} {{{\rm{n}}_{\rm{i}}}} \)and edges\(\sum\limits_{1 \le i < j \le m} {{n_i}} {{\rm{n}}_{\rm{j}}}\).

Step-by-step solution

Definitions.

The vertices of \({{\rm{K}}_{{{\rm{n}}_{\rm{1}}}{\rm{,}}{{\rm{n}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{n}}_{\rm{m}}}}}\)are partitioned into \({\rm{m}}\)sets, with the \({i^{{\rm{th}}}}\)set containing \({{\rm{n}}_{\rm{i}}}\)vertices, and there is an edge connecting two vertices if they are in different subsets.

The number of edges that link to a vertex is the vertex's degree.

The theorem of handshakes The property of an undirected graph with \({\rm{V}}\)vertices and \({\rm{m}}\)edges is:

\({\rm{2m = }}\sum\limits_{{\rm{v}} \in {\rm{V}}} {{\rm{deg}}\left( {\rm{v}} \right)} \)

To determine the number of vertices.

Vertices:

The vertices of \({{\rm{K}}_{{{\rm{n}}_{\rm{1}}}{\rm{,}}{{\rm{n}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{n}}_{\rm{m}}}}}\)are divided into the sets\({V_{\rm{1}}}{\rm{,}}{{\rm{V}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{V}}_{\rm{m}}}\), each of which has \({{\rm{n}}_{\rm{i}}}\)vertices.

The total of the number of vertices of all sets in the partition determines the number of vertices \({\rm{n}}\)in \({{\rm{K}}_{{{\rm{n}}_{\rm{1}}}{\rm{,}}{{\rm{n}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{n}}_{\rm{m}}}}}\):

\({\rm{n = }}{{\rm{n}}_{\rm{1}}}{\rm{ + }}{{\rm{n}}_{\rm{2}}}{\rm{ + \ldots + }}{{\rm{n}}_{\rm{m}}}{\rm{ = }}\sum\limits_{{\rm{i = 1}}}^{\rm{m}} {{{\rm{n}}_{\rm{i}}}} \)

As a result, the number of vertices of the\({{\rm{K}}_{{{\rm{n}}_{\rm{1}}}{\rm{,}}{{\rm{n}}_{\rm{2}}}{\rm{, \ldots ,}}{{\rm{n}}_{\rm{m}}}}}{\rm{is}}\sum\limits_{{\rm{i = 1}}}^{\rm{m}} {{{\rm{n}}_{\rm{i}}}} \).

To determine the number of edges.

Edges:

All vertices in \({{\rm{V}}_{\rm{1}}}{\rm{,}}{{\rm{V}}_{\rm{2}}}{\rm{,}}.......{\rm{,}}{{\rm{V}}_{{\rm{i - 1}}}}{\rm{,}}{{\rm{V}}_{{\rm{i + 1}}}}{\rm{,}}.......{\rm{,}}{{\rm{V}}_{\rm{m}}}\)(excluding those in\({{\rm{V}}_i}\))are connected to a vertex in the set\({{\rm{V}}_i}\). The sum of the number of vertices in all sets (excluding those in\({{\rm{V}}_i}\)) determines the degree of a vertex in\({{\rm{V}}_i}\).

\(v \in {V_i}\)

Using the fact that \({{\rm{V}}_i}\)has\({n_i}\) vertices, calculate the sum of all vertices' degrees.

\(\begin{array}{c}\sum\limits_{{\rm{v}} \in {{\rm{V}}_{\rm{i}}}} {{\rm{deg}}} {\rm{(v) = }}\sum\limits_{{\rm{v}} \in {{\rm{V}}_{\rm{i}}}} {\sum\limits_{{\rm{j}} \ne {\rm{i}}} {{{\rm{n}}_{\rm{j}}}} } \\{\rm{ = }}{{\rm{n}}_{\rm{i}}}\sum\limits_{{\rm{j}} \ne {\rm{i}}} {{{\rm{n}}_{\rm{j}}}} \end{array}\)

Next, calculate the total sum of all partitioning sets:

\(\begin{array}{c}\sum\limits_{v \in V} {\deg } ({\rm{v) = }}\sum\limits_{i = 1}^n {\sum\limits_{v \in {V_i}} {\deg } } (v)\\{\rm{ = }}\sum\limits_{i = 1}^n {{n_i}} \sum\limits_{j \ne i} {{n_j}} \\{\rm{ = }}\sum\limits_{i = 1}^n {\sum\limits_{j \ne i} {{n_i}} } {n_j}\\{\rm{ = }}\sum\limits_{1 \le i < j \le m} {{n_i}} {n_j}\end{array}\)

Result.

Therefore, the number of vertices \(\sum\limits_{{\rm{i = 1}}}^{\rm{m}} {{{\rm{n}}_{\rm{i}}}} \)and edges\(\sum\limits_{1 \le i < j \le m} {{n_i}} {{\rm{n}}_{\rm{j}}}\).