The GATE Grind

GATE 2020 CS – Question 62

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Numerical answer

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 7 to 7

Explanation

$G$ is the complete tripartite graph $K_{1,3,4}$ (the new vertex $s$ is adjacent to everything in $K_{3,4}$).

Minimum number of colours $=\mathbf7$.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →