Topic: Discrete Mathematics / Graph Theory
What is the chromatic number of the graph shown below?
[A planar graph with 8 vertices (a,b,c,d,e,f,g,h) and various interconnecting edges. Specifically, vertices e, f, and g form a $K_3$ (triangle), meaning at least 3 colors are needed.]
- A. 3
- B. 4
- C. 5
- D. 6
Answer: A. 3
Explanation: The chromatic number is the minimum number of colors needed to color the vertices such that no two adjacent vertices share the same color.
The graph contains triangles (e.g., e-f-g), so the chromatic number must be at least 3.
Let's try 3 colors (1, 2, 3): Assign f=1, e=2, g=3.
Since 'a' connects to f and e, a=3.
Since 'd' connects to e and g, d=1.
Since 'h' connects to f and g, h=2.
Since 'c' connects to g and h, c=1.
Since 'b' connects to f and h, b=3.
This assignment successfully colors the entire graph without any two adjacent nodes sharing a color. Therefore, the chromatic number is 3.