You need to track: where you are (vertex ), where you came from (parent to avoid backtracking), and the current consecutive cat count. If vertex has a cat, increment the count. Otherwise, reset it to zero. Before recursing to a child, check if the count exceeds .
If yes, do not recurse (that path is blocked). If you reach a leaf (degree vertex other than root) with valid count, increment the answer. The state flows down the recursion tree, updating at each step.