GATE 2025 DA Q.65: solution and answer

Official answer: 75Source: Official answer key, GATE 2025 DA (IIT Roorkee)

1. Each vertex $i$ has edges only to $i+1$ and $i+2$ (those that exist in $V$). In decreasing order the adjacency list of $i$ is $(i+2,i+1)$, so DFS always tries $i+2$ first.

2. DFS from $0$ therefore descends the even chain $0\to 2\to 4\to \cdots \to 100$. Vertex $100$ has no out-edges, so DFS backtracks.

3. The even vertices discovered after $50$ on this descent are $52,54,\dots ,100$, which is $\frac{100-52}{2}+1=25$ vertices.

4. Back at $98$: its list is $(100,99)$. Vertex $100$ is already discovered, and $99$ is not, so $99$ is discovered. Its neighbours ($100$, and $101$ which does not exist) give nothing new, so DFS returns to $98$ and then to $96$.

5. At every even vertex $2k$ on the way back, the first neighbour $2k+2$ is already discovered and the second neighbour $2k+1$ is not, so $2k+1$ is discovered. Its neighbours $2k+3$ and $2k+2$ are already discovered, so DFS returns. This happens at $98,96,\dots ,0$.

6. Hence the odd vertices $99,97,\dots ,1$ are discovered one by one during the backtrack, in that order. All of them are discovered after the descent has passed $50$, so all $50$ odd vertices come after vertex $50$.

7. Vertices discovered after $50$: $25+50=75$.