StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q32E

Expert-verifiedFound in: Page 734

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Show that C _{n }is chromatically 3-critical whenever n is an odd positive integer,** \(n \ge 3\)

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

Given C_{n}

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

**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.**

Let C_{n }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 C_{5} is 3

The graph is

Similarly ,we will get of graph of C_{3} which is chromatically 3- critical as follows.

This is true for every odd number of vertices.

If we delete any edges of C_{5} and C_{3, }they become chromatically 2-_{ }critical

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

Thus,

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

94% of StudySmarter users get better grades.

Sign up for free