Background:
Consider a connected Feynman diagram $\Gamma$ with $E$ external lines, $I$ internal lines, $L$ loops and $V$ vertices in dimension $D \in \mathbb N$. If you are unfamiliar with the physicist's language, please consult Diagramology by Tim Evans (p.1) to translate it to the language of graph theory.
Define the degree of divergence of $\Gamma$ with $L \gt 0$ as follows.
$$\Delta := DL - 2I$$
In a $\phi^N-$theory, each vertex is required to have exactly $N$ edges locally associated to it. For example, in the $\phi^4-$theory, we can have diagrams such as the following.
In the above examples, $L\gt0$ for the second and fourth diagrams (in fact, $L=1$). These diagrams are respectively quadratically ($\Delta = 2$) and logarithmically ($\Delta = 0$) divergent in $D=4$.
Problem:
We would like to prove that for a $\phi^N-$theory, the degree of divergence is given by:
$$ \boxed{ \Delta = D + V \Big[n \big(\frac{D-2}{D}\big)-D \Big] - E \big(\frac{D-2}{D}\big)} \,.$$
For certain special cases, I have verified that this formula holds true. However, I am not sure how I should go about proving this rigorously.
Kindly help.
Since each vertex comes with $N$ lines crossing at the vertex, we have $NV$ lines to start with, out of which $E$ are chosen to be external. The remaining $(NV-E)$ ones are contracted among themselves to form $I = (NV - E)/2$ internal lines. The factor of one-half is due to the fact that each contraction involves a pair of lines.
As for the number of loops, a physical argument based on the conservation of momentum at each vertex gives that $L=I-(V-1).$ However, as this answer claims, this formula holds true, in general, for planar graphs and is known by the name of 'Euler-Feynman formula'.
Plugging these equations back in the definition gives the required result.
$$ \Delta = D\Big[ \big(\frac N{2} - 1\big)V - \frac E{2} + 1 \Big] + (E-NV)\\ \quad = D + V \Big[n \big(\frac{D-2}{D}\big)-D \Big] - E \big(\frac{D-2}{D}\big) \,.$$
Source: Prahar Mitra, Harvard University [Thanks @Winther for sharing these notes.]