GO Classes 2023 | IIITH Mock Test 1 | Question: 3

Answer 1

Answer: A

Let there be 10 vertexes $\{v_1, v_2, \dots, v_{10}\}$ and their degrees be $\{d_1, d_2, \dots, d_{10}\}$ respectively.

Let total number of edges = $\text{E}$

Now when we remove vertex $v_1$ its corresponding edges will be removed too, now there are 12 edges left, so

$d_1 + 12 = \text{E} \implies d_1 = \text{E } – 12$

Similary we can write these equations for every vertex we remove.

 

Now according to handshaking lemma,

= $\sum(deg) = 2*\text{E}$

= $d_1 + d_2 + \dots + d_{10} = 2*\text{E}$

Putting the values of $d_1, d_2, \dots d_{10}$ in above equation

= $\text{E}-12 + \text{E}-12 + \dots+\text{E} – 11 = 2*\text{E}$

= $4\text{E} – 48 + 4\text{E} – 44 + 2\text{E}-22 = 2*\text{E}$

= $10\text{E} – 112 = 2\text{E}$

= $8\text{E} = 112 \implies\text{E} = 14$

Answer 2

Find the Detailed Video Solution here

$\textbf{Method 1 :}$

Let the vertices be $v_{1}, v_{2}, \dots , v_{10}.$

Let number of edges in $\text{G = E}$

After removing $v_1,$ we get $12$ edges, so, number of edges in $\text{G}  = $E$ = 12 + \deg(v_1)$

Same goes for $v_2,v_3,v_4.$

Similarly we have,

After removing $v_5,$ we get $11$ edges, so, number of edges in $\text{G} = $E$ = 11 + \deg(v_5)$

Same goes for $v_6,v_7,v_8$

Similarly we have,

After removing $v_9,$ we get $10$ edges, so, number of edges in $\text{G} = $E$ = 10 + \deg(v_9)$

Same goes for $v_{10}.$

So, adding all these,

$10 \ast \text{E} = 112 +$ Total degree of $\text{G}$

$\Rightarrow 10 \ast \text{E} = 112 + 2\text{E}$

$\Rightarrow 8 \text{E} = 112$

$\Rightarrow \boxed{\text{E} = 14}$

$\textbf{Method 2 :}$

Let the total degree (summation of degrees of all vertices ) of $\text{G}$ be $\text{S}.$

Let the vertices be $v_1, v_2, \dots, v_{10}.$

When we delete $v_1$ from $\text{G},$ we get a subgraph $\text{A1}$ which has $12$ edges, so,

$\text{S} = 2 \ast \deg(v_1) +$ total degree of $\text{A1}$

$\Rightarrow \text{S}= 2 \ast \deg(v_1) + 24$

When we delete $v_2$ from $\text{G},$ we get a subgraph $\text{A2}$ which has $12$ edges, so,

$\text{S} = 2 \ast \deg(v_2) +$ total degree of $\text{A2}$

$\Rightarrow \text{S}= 2 \ast \deg(v_2) + 24$

So, $\deg(v_1) = \deg(v_2) = \deg(v_3) = \deg(v_4)$

Similarly,

When we delete $v_5$ from $\text{G},$ we get a subgraph $\text{A5}$ which has $11$ edges, so,

$\text{S} = 2 \ast \deg(v_5) +$ total degree of $\text{A5}$

$\Rightarrow \text{S}= 2 \ast \deg(v_5) + 22$

$\Rightarrow \deg(v_5) = \deg(v_1) + 1$

Similarly, $\deg(v_9) = \deg(10) = \deg(v_1) + 2$

So, $\text{S} = 10 \ast \deg(v_1) +  8 =  2 \ast \deg(v_1) + 24
\deg(v_1) = 2$

So, the degree sequence is $2, 2, 2, 2, 3, 3, 3, 3, 4, 4.$

So, number of edges in $\text{G} = 14.$

Find the Detailed Video Solution here