GATE CS 2014 Set 3 — Question 23

In DFS, the recursion depth at any moment equals the number of vertices on the current chain of calls, which is a simple path in the graph. The maximum possible depth is therefore the number of vertices on the longest simple path, since a suitable start vertex and neighbour order lets DFS follow any simple path.The graph has 21 vertices: two $3 \times 3$ grids (9 each), a middle vertex joining the bottom-right corner of the left grid to the bottom-left corner of the right grid, a pendant vertex above the middle vertex, and a pendant vertex attached to the middle-right vertex of the right grid.Count the vertices on the longest simple path.

• Pendant above the middle vertex. It has degree 1 and its only neighbour, the middle vertex, separates the two grids. A path containing it must end there, so it can visit only one grid: at most $1 + 1 + 9 + 1 = 12$ vertices. The longest path therefore avoids it.
• Upper bound. Colour each $3 \times 3$ grid like a chessboard: the 4 corners and the centre (5 vertices) get one colour, the 4 edge-midpoints the other. A path inside the grid alternates colours, so a path through all 9 grid vertices must start and end at corners or the centre. A path that stays on one side of the middle vertex has at most $9 + 1 + 1 + 1 = 12$ vertices, so consider a path that crosses from one grid to the other; it enters the right grid at its bottom-left corner. If it also takes the right pendant, it must leave the grid at the middle-right vertex (an edge-midpoint), so it covers at most 8 right-grid vertices: $9 + 1 + 8 + 1 = 19$. Without the right pendant it has at most $9 + 1 + 9 = 19$ vertices.
• The bound is reached. Start at the top-left vertex of the left grid and go through it row by row: top row left to right, middle row right to left, bottom row left to right. That ends at its bottom-right corner (9 vertices). Then take the middle vertex (1), enter the right grid at its bottom-left corner and go up the left column, then along the top row, down to the middle-right vertex, left to the centre, down to the bottom-middle vertex, and right to the bottom-right corner (9 vertices). Total $9 + 1 + 9 = 19$.

DFS can follow exactly this path if it starts at that corner and always picks the next vertex on the path first, so the maximum recursion depth (including the initial call) is 19. An exhaustive search over all simple paths in the graph confirms that 19 is the maximum.Answer: 19