GATE Overflow Test Series | Mixed Subjects | Test 2 | Question: 7

Question

If a simple graph $G,$ has $10$ vertices and $11$ edges, the number of edges in the complement of $G$ will be _______

Answer 1

A complete graph of $10$ vertices will have $10 \times 9/2 = 45$ edges. Since $G$ has $11$ edges, complement of $G$ will have $45-11 = 34$ edges.

Answer 2

Given that, simple graph $G$ has $n = 10$ vertices, $e = 11$ edges.

Let say, the number of edges in the complement of $G$ is $x.$

We know that, $e + x = \;^{n}C_{2}$

$\implies e + x = \dfrac{n(n-1)}{2}$

$\implies 11 + x = \dfrac{10\cdot 9}{2} = 45$

$\implies x = 45 – 11 = 34.$

Hence, he number of edges in the complement of $G$ is $x = 34$ edges.

So, the correct answer is $34.$