Assume that $A$ is an uncountable set, $B$ is a countable one, and $G \subset A \times B$ is a relation between elements of $A$ and $B$.
Suppose that $\forall a \in A$, $\exists b \in B$ such that $(a, b) \in G$.
Then $\exists a_1 \neq a_2 \in A$, $\exists b \in B$, such that both $(a_1, b) \in G$ and $(a_2, b) \in G$.
If I use choice axiom, I have the existence of a function $f : A \rightarrow B$ such that $(a, f(a)) \in G$ and such a function cannot be injective because $A$ is not countable, but $B$ is, so the statement is proved.
Is there a way to avoid it ?
We don't need to use the axiom of choice here. The countability of $B$ ensures the existence of a well-order on $B$ without choice (the precise argument depends on how exactly countability is defined; if it's the existence of an injection $\iota \colon B \to \mathbb{N}$, we directly have the inherited well-order on $\iota(B)$, if it's defined differently, how?), and thus we can define
$$f(a) = \min \{ b \in B : (a,b) \in G\}$$
with that well-order. If $f$ were injective, it would follow that $A$ is countable.