A colouring answer is not complete until you have both a lower bound and an actual colouring that attains it. The rules also change when the question moves from vertex colouring to edge colouring or asks about a greedy algorithm. Attempt each question yourself before opening its explanation.
Graph colouring at GATE keeps returning to five asks: whether the graph is bipartite, what a drawn figure forces, what the Four Colour Theorem does and does not promise, how the greedy order changes the count, and what changes when colours sit on edges instead of vertices. Use the broader Graph Theory MCQ set for mixed practice, and GATE Guidance by Sanchit Sir for a sequenced Discrete Mathematics and Graph Theory course path.
1. Begin with bipartite graphs and cycle parity
Q1. MCQ, GATE Computer Science 2009
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n >= 2.
(a)
n-1(b)
3(c)
2(d)
n
Answer: (c) 2. A graph with no odd cycle is bipartite, so its two independent sets give a 2-colouring. Because the graph is connected and n >= 2, it has an edge whose endpoints require different colours. Thus both bounds are 2.
Q2. MCQ, GATE Computer Science 2002
The minimum number of colors required to color the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same color is
(a)
2(b)
3(c)
4(d)
n − 2⌊n/2⌋ + 2
Answer: (d). For n=6, the expression gives 6 − 2(3) + 2 = 2. Two colours alternate around an even cycle and the last vertex receives a colour different from the first. For n=5, it gives 5 − 2(2) + 2 = 3. Alternation makes the fifth vertex match the first, so a third colour is necessary. In general, the expression is 2 for even n and 3 for odd n.
2. Test 2-colourability as both a theorem and an algorithm
Q3. MSQ, GATE Computer Science Set 1, 2026
An undirected, unweighted, simple graph G(V,E) is said to be 2-colorable if there exists a function c:V→{0,1} such that for every (u,v)∈E, c(u)≠c(v). Which of the following statements about 2-colorable graphs is/are true?
(a) If G is 2-colorable, then G may contain cycles of odd length
(b) If G is 2-colorable, then G may contain cycles of even length
(c) An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V|+|E|), if G is represented as an adjacency list
(d) An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|E|log|V|), if G is represented as an adjacency list
Answer: (b) and (c). Take C4 = (v1,v2,v3,v4,v1) and assign v1=0, v2=1, v3=0, v4=1. This proves that a 2-colourable graph may contain an even cycle. On an odd cycle, alternating colours returns to the starting edge with equal colours at both ends.
BFS or DFS performs the same test component by component. With an adjacency list, every vertex is visited once and every edge is examined a constant number of times, so the running time is Θ(|V|+|E|), not Θ(|E| log |V|).
3. Read a pictured graph and prove a lower and upper bound
Q4. NAT, GATE Computer Science Set 2, 2024
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is _________
Answer: 2. Label the leftmost upper vertex v1 and continue clockwise to v8. Give colour A to the odd-indexed vertices and B to the even-indexed vertices. Every edge of the outer eight-cycle joins consecutive indices, and the seven chords are v1v4, v1v6, v2v5, v2v7, v3v6, v4v7 and v5v8, so each of the fifteen edges joins an odd index to an even index. That makes this a valid 2-colouring, and the graph has an edge, which rules out one colour. Therefore χ(G)=2.
Q5. NAT, GATE Computer Science 2018
The chromatic number of the following graph is _______.
Answer: 3. The cycle a-b-c-a is a triangle, so at least three colours are required. Now use a=Red, b=Blue, c=Green, d=Red, e=Blue, f=Green. Every drawn edge joins different colour classes. In particular, c-e is Green-Blue, c-d is Green-Red, b-d is Blue-Red and d-f is Red-Green. Thus three colours suffice.
The reusable method is simple: exhibit a clique or odd cycle for the lower bound, then write an explicit colouring for the upper bound. The Graph Theory deep-dive develops the same proof habit across the wider topic.
4. Move from 3 colours to a forced 4-colouring
Q6. MCQ, GATE Computer Science and Information Technology 2008
What is the chromatic number of the following graph?
(a)
2(b)
3(c)
4(d)
5
Answer: (b) 3. The cycle top-left → top-middle → top-right → middle-right → bottom-right → top-left has length 5, so two colours cannot work. Checkerboard-colour the 3 × 3 grid with A and B. The curved edge joins two vertices of the same colour, so recolour one endpoint C. Its grid neighbours have the other colour, making the result proper. Hence three colours are necessary and sufficient.
Q7. MCQ, GATE Computer Science 2004
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is
(a)
2(b)
3(c)
4(d)
5
Answer: (c) 4. Label the inner square UL, UR, LR, LL clockwise and the outer vertices T, R, B, L. T joins UL, UR, L and R. L joins UL, LL, T and B. R joins UR, LR, T and B. B joins LL, LR, L and R. Assume a 3-colouring. In triangle T-UL-UR-T, set T=3, UL=1, UR=2 without loss of generality. Since L touches T and UL, L=2. Triangle L-UL-LL-L forces LL=3. Since B touches L and LL, B=1. Triangle B-LL-LR-B forces LR=2. Vertex R touches colour 3 at T, colour 1 at B and colour 2 at UR, so no colour remains. This contradiction gives a lower bound of 4.
Four colours also suffice: UL=LR=1, UR=LL=2, T=B=3, and L=R=4. Each colour class is a non-adjacent pair, including T/B and L/R, so every drawn edge has differently coloured endpoints.
5. Separate “this graph” from “every planar graph”
Q8. NAT, GATE Computer Science Set 2, 2016
The minimum number of colours that is sufficient to vertex-colour any planar graph is _____________ .
Answer: 4. The planar graph K4 has four mutually adjacent vertices, so no universal guarantee below four is possible. The Four Colour Theorem provides the matching upper bound: every planar graph is 4-colourable. It says at most four colours are sufficient, not that every planar graph has chromatic number 4.
6. Do not confuse greedy vertex colouring with edge colouring
Q9. MSQ, GATE Computer Science 2023
Let G be a simple, finite, undirected graph with vertex set {v1,...,vn}. Let Δ(G) denote the maximum degree of G and let N = {1, 2,...} denote the set of all possible colors. Color the vertices of G using the following greedy strategy:
for i = 1,...,n
color(vi) ← min{j ∈ N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE?
(a) This procedure results in a proper vertex coloring of G.
(b) The number of colors used is at most Δ(G) + 1.
(c) The number of colors used is at most Δ(G).
(d) The number of colors used is equal to the chromatic number of G.
Answer: (a) and (b). When a vertex is processed, at most Δ(G) neighbour colours are forbidden, so one of 1,...,Δ(G)+1 remains available. Choosing an unused neighbour colour also makes the result proper.
For the path with edges a-b, b-c, c-d, process vertices in the order a,d,b,c. Greedy assigns a=1, d=1, b=2, then c=3 because c sees colours 2 at b and 1 at d. It uses three colours even though Δ=2 and χ(P4)=2. This one trace disproves both (c) and (d).
Q10. NAT, GATE Computer Science 2020
Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour G is _________ .
Answer: 7. Vertex s has degree 3+4=7, so its seven incident edges require seven distinct colours. This proves the lower bound.
For sufficiency, call the size-3 side u1,u2,u3 and the size-4 side w1,w2,w3,w4. Edge-colour K3,4 as follows:
Edge from | w1 | w2 | w3 | w4 |
|---|---|---|---|---|
u1 | 1 | 2 | 3 | 4 |
u2 | 2 | 3 | 4 | 1 |
u3 | 3 | 4 | 1 | 2 |
The missing colours at w1,w2,w3,w4 are respectively 4, 1, 2 and 3. Assign those colours to s-w1,s-w2,s-w3,s-w4. Each ui already sees colours 1 to 4, so assign colours 5, 6 and 7 to s-u1,s-u2,s-u3. All seven edges at s are distinct, and no new edge repeats a colour at its other endpoint. Therefore seven colours attain the lower bound.
7. The short version: turn the ten answers into a revision loop
Question cue | Theorem or construction used | Mistake to avoid |
|---|---|---|
Odd-cycle or bipartite clue | No odd cycle iff bipartite | Forgetting the one-colour lower bound |
Even versus odd cycle | Alternate two colours | Ignoring the closing edge |
BFS two-colouring | Process every vertex and edge | Adding an unnecessary log factor |
Lower-bound witness | Find a clique or odd cycle | Giving only a guessed colour count |
Explicit upper-bound colouring | List every colour class | Failing to check a chord |
Planar upper bound | Four Colour Theorem plus | Reading “at most four” as “exactly four” |
Greedy order dependence | Trace the stated order | Assuming greedy is always optimal |
Vertex versus edge colouring | Check what receives colours | Applying a vertex theorem to edges |
Redo only the questions you missed after 48 hours. Then use the GATE Test Series for timed application and the GATE CS category to place graph colouring in the wider preparation path. For solved GATE questions on the neighbouring logic topic, continue with Propositional and Predicate Logic MCQs.
The short version is to ask what proves fewer colours cannot work, then what construction proves your claimed number does work. Keep vertex colouring, greedy colouring and edge colouring separate, and these answers become reusable methods.
