Prove that the chromatic number of a cycle of odd length is 3. I know that this

Question

Prove that the chromatic number of a cycle of odd length is 3. I know that this proof is probably extremely simple, but I cannot think of how to accomplish it. Help PLEASE!!!

Explanation / Answer

Theorem 9: The chromatic number of Cn is 2 if n is even, and 3 if n is odd. Proof: First note that the chromatic number must be at least 2 for any graph which has an edge in it, including all cycles. We now prove the theorem by induction on n. We will consider two base cases, C3 and C4. C3 is isomorphic to K3 which has chromatic number 3. C4 can be colored with two colors by giving opposing corners of the square the same color. For n > 4, we can take a coloring of Cn-2 and insert 2 adjacent vertices and edges and then color the new vertices appropriately to get a coloring of Cn. Thus the chromatic number of Cn is not greater than that of Cn-2. In the case where n is odd, note that if Cn had chromatic number 2, we could remove two adjacent vertices and edges to get a 2-coloring of Cn-2 which contradicts the inductive hypothesis since n-2 must be odd if n is odd. QED Graphs which are 2-colorable are sufficiently important that they have a special name.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.