The chromatic number of the following graph is _____. The graph has 6 vertices a, b, c, d, e, f with edges: a-e, a-b, a-c, c-e, c-d, c-b, b-d, b-f, d-f, e-f.

GATE 2018 · Discrete Mathematics · Graph Coloring · medium

Answer: 3

1. Lower bound from a clique: Vertices a, b, c are pairwise adjacent (a-b, b-c, a-c), so they form K_3 and need 3 distinct colours: chi >= 3.
2. Exhibit a 3-colouring: Check each edge: a-e (1,2), a-b (1,2), a-c (1,3), c-e (3,2), c-d (3,1), c-b (3,2), b-d (2,1), b-f (2,3), d-f (1,3), e-f (2,3) - all endpoints differ.