GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 13

Answer 1

Chromatic number of $3$ because the color of $h$ can be given to $c$ as well. And color of $h$ can not be given to $\{a,b,d,e,f,g\}.$ Note that $\{a,b,d,e,f,g\}$ is a cycle so it can is two colorable, so, total $3$ colors.

One of the Maximum Matching is $\{ag, bd, ce, fh\}$

So, total $3+4 = 7$ is the answer.

Comments

Useful method for finding chromatic number:-

Always find the size of largest independent sets and the number of indipendent sets thus formed will give you the chromatic number.

---

For more: Find the chromatic number and matching number of a graph