I am trying to understand the recursive formula for defining tree-depth as suggested in Sparsity by Nešetřil, Jaroslav, Ossona de Mendez, Patrice. I am trying to implement in python but I am slightly confused with the formula.
For a graph G: $$ td(G) = \begin{cases} 1, & \text{if $ |G| = 1; $} \\ 1 + min_{v\in V(G)} td(G-v) & \text{if $G$ is connected and $|G|>1$; }\\ max_{i = 1}^{p} td(G_i) & \text{otherwise; } \end{cases} $$ (where $G_1,..,G_p$ are connected components of a G)
I am struggling to understand the recursive case in the formula where $|G| > 1$. Usually when $min$ or $max$ have two values to compare, but how do I interpret the $min$ function here?
I'll show you how to do the example mentioned in your comment. After that, I think you'll be able to do any example.
If we look at the three case limbs in the definition, we see that $|G|=3>1,$ and that $G$ is connected, so it's the second case that applies. We have to find the minimum value of $td(G-v)$ where $v\in\{1,2,3\}.$ Let $G_v=G-v,\ v\in\{1,2,3\}.$ Then $G_1$ consists of two isolated vertices and $G_2$ and $G_3$ each consist of a single edge.
To compute $td(G_1),$ we note that $G_1$ is not connected, so the third case limb applies. We need the maximum of the tree depth of each component, and the first case limb tells us the both of these are equal to $1$. Of course, the maximum of $1$ and $1$ is $1$, so $td(G_1)=1.$
For $td(G_2)$ we see that the second case limb applies, and again, we have to find the minimum tree depth of the graphs we get by deleting each of the vertices. In each case we get a graph with consisting of a single vertex vertex, and the tree depth of each is $1$ by case limb $1$. Of course, the minimum of $1$ and $1$ is $1$, and we have to add $1$ to this, according to the definition in case limb $2,$ so the tree depth of $G_2$ is $2$.
$G_3$ is isomorphic to $G_2,$ so if we carry ou the computation we will also get $td(G_3)=2.$
Now we pop back up to the top level. We have $$td(g)=1+\min(\{td(G_1),td(G_2),td(G_3)\})=1+\min({1,2,2})=1+1=2$$