What is the proper runtime for visiting all outgoing edges in an adjacency list?
You're right that $\Theta(\deg^+ v)$ is a bit sloppy, but it is usually understood that $\Theta(\deg^+ v)$ is actually $\Theta(1 + \deg^+ v)$. Perhaps it's better to use the more accurate $\Theta(1 + \deg^+ v)$.

You're also right that more formally a $\Theta(\cdot)$ notation should state the underlying variable, but here there is only one variable and so no confusion can arise. Also, since $\deg^+ v$ is always non-negative, the simpler definition of $\Theta(\deg^+ v)$ - there exists $C &gt; 0$ such that the running time is at most $C \deg^+ v$ - is unambiguous. That's also how we should understand expressions like $\Theta(n + m)$, where the two variables $n,m$ are independent.