Question

Show that C_nis chromatically 3-critical whenever n is an odd positive integer,\(n \ge 3\)

Short answer

C_nis chromatically 3-critical whenever n is an odd positive integer, \(n \ge 3\)

Step-by-step solution

Note the given data

Given C_n

We need to show thatC_nis chromatically 3-critical whenever n is an odd positive integer, \(n \ge 3\)

Definition

The chromatic number of a graph is the smallest number of colors that can be used in an edge coloring of the graph. The edge chromatic number of a graph is denoted by \(\chi \left( G \right)\)

A connected graph G is called Chromatically k-critical if the chromatic number of G is k , but for every edge of G , the chromatic number of the graph obtained by deleting this edge from G is k -1.

Calculation

Let C_nrepresents a cycle of edges of size n

i.e, graph with n vertices \({v_1},{v_2},{v_3},......{v_n}\)and edges\(\left\{ {{v_1},{v_2}} \right\},\left\{ {{v_2},{v_3}} \right\},.........\left\{ {{v_n},{v_1}} \right\}\)

as a circle is not possible with 2 points so n must be 3 or greater than 3

ie\(n \ge 3\)

let n =5 and proceed as follows

• Pick a vertex and color it red
• Proceed clockwise in the graph and assign the second vertex as blue
• Continue in the clockwise direction and assign the third vertex color red(since it is not adjacent to vertex 1).

• Fourth vertex color blue
• Finally the fifth vertex, which is not adjacent to first vertex cannot be colored either blue or red as it is adjacent to both the vertex, So take another color say yellow

Therefore, the chromatic number of C₅ is 3

The graph is

Similarly ,we will get of graph of C₃ which is chromatically 3- critical as follows.

This is true for every odd number of vertices.

If we delete any edges ofC₅ and C_3,they become chromatically 2-critical

These figures show that C_nis chromatically 3-critical whenever n is an odd positive integer,\(n \ge 3\)

Thus,

C_nis chromatically 3-critical whenever n is an odd positive integer, \(n \ge 3\)