GATE 2020 CS Q.52: solution and answer

GATE 2020 · CSQ.52 · 2 marks · NAT

Graph $G$ is obtained by adding vertex $s$ to $K_{3, 4}$ and making $s$ adjacent to every vertex of $K_{3, 4}$ . The minimum number of colours required to edge-colour $G$ is ____.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The minimum number of colours needed to edge-colour $G$ is $7$ .

Official answer: 7Source: Official answer key, GATE 2020 CS (IIT Delhi)

$G$ has $8$ vertices: the parts $A = {a_{1}, a_{2}, a_{3}}$ , $B = {b_{1}, b_{2}, b_{3}, b_{4}}$ of $K_{3, 4}$ , and $s$ joined to all seven of them.
Degrees: $de g s = 7$ , $de g a_{i} = 4 + 1 = 5$ , $de g b_{j} = 3 + 1 = 4$ . So $Δ (G) = 7$ .
Lower bound: the $7$ edges at $s$ share the endpoint $s$ , so they need $7$ distinct colours. Hence $χ^{'} (G) \geq Δ (G) = 7$ .
Upper bound: first edge-colour $K_{3, 4}$ with the four colours ${0, 1, 2, 3}$ by giving $a_{i} b_{j}$ the colour $(i + j) mod 4$ . At $a_{i}$ the four edges get $i + 1, i + 2, i + 3, i + 4 (mod 4)$ , which are all different. At $b_{j}$ the three edges get $j + 1, j + 2, j + 3 (mod 4)$ , which are all different. So this colouring is proper.
Vertex $b_{j}$ uses $j + 1, j + 2, j + 3 (mod 4)$ and misses colour $j mod 4$ . Give $s b_{j}$ that colour. Then $s b_{1}, \dots, s b_{4}$ get the four different colours $1, 2, 3, 0$ , and each $b_{j}$ still has all its edges in different colours.
Each $a_{i}$ already uses all of $0, 1, 2, 3$ . Colour $s a_{1}, s a_{2}, s a_{3}$ with the three new colours $4, 5, 6$ . These differ from each other and from the colours $0, 1, 2, 3$ on the edges $s b_{j}$ , so the colours at $s$ are all different. Each $a_{i}$ sees its four old colours plus one new colour, so it is also proper.
This is a proper edge-colouring with $7$ colours, so $χ^{'} (G) \leq 7$ . Together with the lower bound, $χ^{'} (G) = 7$ .

KEY IDEA

The vertex $s$ has degree $7$ , which forces at least $7$ colours. Then build a $7$ -colouring directly. Colour $K_{3, 4}$ with $4$ colours so that each $b_{j}$ misses a different colour. Give those missing colours to the edges $s b_{j}$ . The three edges $s a_{i}$ take three new colours.

WATCH OUT FOR

Using $Δ + 1 = 8$ because $G$ is not bipartite. Vizing's theorem only says $χ^{'}$ is $Δ$ or $Δ + 1$ . Here an explicit colouring shows $Δ$ colours are enough, so $G$ is Class 1.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 14 Graph theory questions, with notes

GATE 2020 CS Q.52: solution and answer

Answer and solution

More Graph theory questions