ISRO CS 2023 Q.6: solution and answer

Official answer: ASource: ISRO's revised and final answer key of 16 February 2024

1. A simple graph has no loops and no parallel edges, so for each unordered pair of distinct vertices there are only two possibilities: the edge is present or it is absent.

2. With $n$ labelled vertices the number of unordered pairs is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$.

3. The choices for different pairs are independent, and each pair has 2 choices. By the multiplication principle the number of distinct simple graphs on the $n$ labelled vertices is $$2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}=2^{n(n-1)/2}.$$

4. Check with $n=3$: there are 3 possible edges, so $2^3=8$ graphs, and the formula gives $2^{3\cdot 2/2}=2^3=8$.

5. The other options do not match this count. Option (b) uses $(n-1)/2$ in the exponent, which is not the number of vertex pairs (for $n=3$ it gives $2^1=2$). Option (c) has $n(n+1)/2=\left(\genfrac{}{}{0ex}{}{n}{2}\right)+n$ in the exponent, which would also allow a loop at each vertex, and a simple graph has none. Option (d) has $n(n+1)$, twice that count.

6. Hence the maximum number of simple graphs is $2^{n(n-1)/2}$, option (a).