If we have graph $G=(V,E)$, and we also have some graph algorithm which complexity is $O( |E|*\Delta)$ or $O(|V|*\Delta)$, so it depends on the $\Delta$ value, where $\Delta$ is a maximum degree of a graph ($max\ {deg(v)}$).
Is this algorithm pseudo-polynomial or just polynomial ?
Edited: By polynomial I mean polynomial time where the input is $V$ and $E$.
P.S.
I think it's polynomial because $\Delta$ is not a numerical value of some part of the input, but I'm not sure.
I think part of what is confusing you is that when you say "polynomial" you should say "polynomial in what". For example, our standard algorithms for prime factorization take "polynomial time"...in the number itself. But in that field "polynomial" means "polynomial in the number of digits".
In your case, note $\Delta \leq |V|$, so something $O(|E| |V|)$ is polynomial in $|E|$ and $|V|$.