GATE CSE 2020 Q62: Edge chromatic number of K(3,4) plus a vertex joined to all

Engineering Mathematics
2 marks
NAT
No negative marking

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 _______.

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 7 (official GATE 2020 final answer key)

Concept used: Vizing's theorem: the edge chromatic number is the maximum degree $\Delta$ or $\Delta + 1$ .

First step: Find the degrees: $s$ has degree 7, which is the maximum; then try to build a colouring with 7 colours.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

PracticePractise Engineering Mathematics questions →Full paperAll GATE CSE 2020 questions →

GATE CSE 2020 Q62: Edge chromatic number of K(3,4) plus a vertex joined to all

Question

Full step-by-step solution

More Engineering Mathematics PYQs