Question

Show that the edge chromatic number of a graph must be at least as large as the maximum degree of a vertex of the graph.

Short answer

The edge chromatic numbers will be at least d

Step-by-step solution

Given Information.

We are given a graph G.

We are also given that the maximum degree of vertex of this graph d.

Definition of Edge chromatic numbers and degree of vertex

The edge chromatic numbers, sometimes also called 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.

The number of edges connecting it is called degree of vertex.

Solution

To prove:

Edge chromatic number of G is at least d.

Proof:

Since we are given that the maximum degree of vertex of the graph is d, there should be a vertex v, having the degree d. Also there is no other vertex with a larger degree than vertex v.

Now, each of these edges will need a different chromatic color since we give every edge of the same vertex a different color.

So, by the definition of edge chromatic number, the edge chromatic number is at least d.

The final solution is

The edge number is at least d