Question

Find the edge chromatic number of k_n when n is a positive integer.

Short answer

The edge chromatic numbers are

If n is even: n-1

If n is odd: n

Step-by-step solution

Given Information.

K_n with n vertices and edges between every pair of vertices.

Definition of Edge chromatic numbers.

The edge chromatic numbers, sometimes alsocalled the chromatic index, of a graph is the fewest number of colors necessary to color each edge of. such that no two edges incident on the same vertex have the same color.

Explanation.

With all other(n-1 )vertices, every vertices of K_nis connected by an edge to it. All n-1 edges which connected to a vertex will have a different color and then an edge coloring has at least n-1 different colors.

Even number of vertices:

Let n be even

Total number of edges will be: n(n-1 ) /2

Now we know that there are no more than n/2 edges coloured the same so, there will be (n-1) different colors possible in an edge coloring.

So, the edge chromatic number is (n-1 ) .

Explanation.

Odd number of vertices:

Let n be odd

Here, there will be no more than n(n-1 ) /2 edges coloured the same as n is odd.

So, there will be different colors possible in an edge coloring.

So, the edge chromatic number is n.

The final solution is

The edge chromatic numbers are

If nis even: n-1

If n is odd: n