GO Classes Scholarship 2023 | Test | Question: 9

Answer 1

For this question we just need to found Chromatic number and Clique number .

We know that 

Matching number(M)+Edge cover number (E)=Number of vertices(n)

Independence Number(I)+ vertex cover number(B)= number of vertices(n)

Given expression;

$M+C+I+S+B+E$

=$(M+E)+(I+B)+S+C$

=$n+n+S+C$

=$2n+S+C$

Now the given graph don’t have any odd length cycle So It is bipartite graph.

We know that bipartite with at least one edge has chromatic number(S) =$2$.

Now clique number(C) for any bipartite graph with at least one edge is 2 as the largest complete graph it contains is $K_{2}$ because from $K_{3}$ any complete graph contains an odd length cycle which is not bipartite.

So our required answer is :-

=$2*8+2+2$                 [as $n=8$]

=$20$

Comments

That’s excellent answer & so efficient.

---

@Deepak Poonia Thank u sir

Answer 2

The observation is that the given graph is bipartite, as there is No odd cycle in the given graph.
Also, $\text{G}$ is isomorphic to hypercube graph $\text{Q3}.$ And $\text{Q3}$ is bipartite.
Hence, $\mathrm{C}=2, \mathrm{I}=4, \mathrm{~S}=2, \mathrm{~B}=4, \mathrm{E}=4$
So, Maximum Matching $=\{12,34,56,78\}$, Hence, matching number $=4$
Hence, the answer is $20 .$

$\text{Q1, Q2, Q3}$ are planar graphs. $\text{Q4, Q5}$ are not planar.