Question

The chromatic number of a wheel graph on \( n \) vertices denoted by \( W_n \) is:

• A. \( n \)
• B. \( 3 \) when \( n \) is even and \( 4 \) when \( n \) is odd
• C. \( n - 1 \)
• D. \( 3 \) when \( n \) is odd and \( 4 \) when \( n \) is even

Hint:

The chromatic number of a wheel graph follows a simple rule:
- \( \chi(W_n) = 3 \) if \( n \) is even.
- \( \chi(W_n) = 4 \) if \( n \) is odd.

Answer 1

The Correct Option is B

Step 1: Understanding the chromatic number of a wheel graph A wheel graph \( W_n \) consists of a cycle \( C_{n-1} \) with an additional central vertex connected to all other vertices.
Step 2: Determining the chromatic number
- If \( n \) is even, the cycle \( C_{n-1} \) is odd in length and requires 3 colors. The center vertex can reuse an existing color. Thus, the chromatic number is 3.
- If \( n \) is odd, the cycle \( C_{n-1} \) is even in length and can be colored with 2 colors. However, the central vertex needs an additional color, making the chromatic number 4.

Step 3: Evaluating the Options
- Option (A) \( n \): Incorrect, as chromatic number doesn't always equal \( n \).
- Option (B) \( 3 \) when \( n \) is even and \( 4 \) when \( n \) is odd: Correct based on analysis.
- Option (C) \( n - 1 \): Incorrect, does not follow chromatic number rules for wheel graphs.
- Option (D) \( 3 \) when \( n \) is odd and \( 4 \) when \( n \) is even: Incorrect as it misinterprets even and odd cases.