• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q32E

Expert-verified Found in: Page 734 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Show that Cn is chromatically 3-critical whenever n is an odd positive integer, $$n \ge 3$$

Cn is chromatically 3-critical whenever n is an odd positive integer, $$n \ge 3$$

See the step by step solution

## Step 1: Note the given data

Given Cn

We need to show that Cn is chromatically 3-critical whenever n is an odd positive integer, $$n \ge 3$$

## Step 2: 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.

## Step 3: Calculation

Let Cn represents 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 C5 is 3

The graph is Similarly ,we will get of graph of C3 which is chromatically 3- critical as follows. This is true for every odd number of vertices.

If we delete any edges of C5 and C3, they become chromatically 2- critical These figures show that Cn is chromatically 3-critical whenever n is an odd positive integer, $$n \ge 3$$

Thus,

Cn is chromatically 3-critical whenever n is an odd positive integer, $$n \ge 3$$ ### Want to see more solutions like these? 