Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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

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

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Note the given data

Given C_n

We need to show that C_nis 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 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 of C₅ 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\)

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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

Step by Step Solution

Step 1: Note the given data

Step 2: Definition

Step 3: Calculation

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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

Step by Step Solution

Step 1: Note the given data

Step 2: Definition

Step 3: Calculation

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths

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