Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _______.

The recursion depth of Depth First Search (DFS), including the initial call, is equal to the number of vertices in the longest simple path that can be traversed by DFS.

Let us analyze the graph:

1. It contains a left $3 \times 3$ grid of $9$ vertices.

2. A connector part consisting of $2$ vertices: one on the bottom row connecting the left grid to the right grid, and one vertex above it (a leaf connected only to the bottom connector vertex).

3. A right $3 \times 3$ grid of $9$ vertices.

4. A leaf vertex attached to the rightmost-middle vertex of the right grid.

Total number of vertices in the graph is $9 + 2 + 9 + 1 = 21$.

The graph is bipartite. A simple path in a bipartite graph cannot visit all vertices if certain dead-end/leaf configurations force a choice where some vertices must be left unvisited. Specifically, we can find a simple path that visits:

• All $9$ vertices of the left $3 \times 3$ grid (by a Hamiltonian path starting at the top-left vertex and ending at the bottom-right vertex).

• The $1$ bottom connector vertex (leaving the isolated vertical leaf unvisited, or if we start at the leaf, we cannot visit the entire left grid).

• All $9$ vertices in the right $3 \times 3$ grid.

Total maximum number of vertices on a single simple path $= 9 + 1 + 9 = 19$.

Therefore, the maximum possible recursion depth is 19.