Answer to Question #270910 in Combinatorics | Number Theory for vikash

Question

Define K-edge colouring and K-vertex colouring of a graph. Find the edge chromatic numbers to colour the edges of the complete graph with four and five vertices

Answer 1

Edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color.

An edge coloring with k different colors is called a k-edge-coloring.

A proper k-vertex coloring of a simple graph G = (V,E) is defined as a vertex coloring from a set of k colors such that no two adjacent vertices share a common color.

Edge chromatic number is the number of distinct colors in a minimum edge coloring.

Chromatic number of complete graph K_n is n

So,

for complete graph with four vertices chromatic number is 4

for complete graph with five vertices chromatic number is 5