The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is A. 2 B. 3 C. 4 D. 5 (The graph has a top apex and a bottom apex, each joined to all four vertices of a central square; the central square's four vertices form a 4-cycle.)
Locate a K4: Take the top apex T, the bottom apex B, and two adjacent square vertices u and v. T and B are each joined to u and v; u and v are joined by a square edge; and T-B... the two apexes share both u and v as common neighbours. T, u, v plus either apex give a set of four mutually adjacent vertices, a K4. So at least 4 colours are needed.
Colour with exactly 4: Assign colour 1 to the top apex, colour 2 to the bottom apex. Around the square use colours 3,4,3,4 in cycle order so adjacent corners differ; each corner also differs from both apexes (colours 1,2). No edge has matching endpoints, so 4 colours suffice.
Conclude: Since 4 colours are both necessary and sufficient, the minimum number of colours is 4, giving answer C.