Suppose at each step $n$ of a proof by induction, we have a set $X_n$. Also, $X_{n} \subseteq X_{n+1}$. Is induction enough to give us $\bigcup_{n \in \mathbb{N}} X_n$? Or rather, when is it enough?
For example, in the proof of Konigs' Lemma, the answer is no. In it, we are trying to prove that an tree with countably infinite vertices and finite levels has a path of infinite length. At each step of the induction, we have a path of length $n$. We can see this as a set $X_n$ of nodes of the tree. The next path/set $X_{n+1}$ is chosen such that $X_n \subseteq X_{n+1}$. To get the path of infinite length, $\bigcup_{n \in \mathbb{N}} X_n$, we need the axiom of countable choice.
On the other hand, in the proof of the uniqueness of the Rado graph, for each $n$, we have a graph homomorphism from a vertex set $V_n$ to another set of vertices $W$, $\varphi_n: V_n \to W$, such that $V_{n} \subseteq V_{n+1}$. Then, we union these $\varphi = \bigcup_{n \in \mathbb{N}} \varphi_n$ to get an isomorphism between the two graphs with vertex sets $V$ and $W$ respectively. This does not require the axiom of choice.
What is the key difference between these two examples that makes one require the axiom of choice while the other doesn't?
If your sequence is given, then $\bigcup_{n\in\omega}X_n$ exists, yes. It is enough. If you have an inductive definition which goes from a given $X_n$ to $X_{n+1}$, then induction itself is not enough to give you the wanted sequence, and therefore its union. You need to show that you can get "through the induction" using very particular choices, which amounts to proving that the sequence that you want exists.
And more generally if you have a sequence of sets, this really means that there is a function whose domain is $\omega$ (or some other index set) and its range is some family of sets. By replacement axioms the range of the function is a set as well, and by the axiom of union, its union exists.
Therefore if you have $X_n$ for $n\in\omega$, then $\bigcup_{n\in\omega}X_n$ is a set as well.
Note that the difficulty where the axiom of choice gets into the proofs is that the induction may not have a "clear choice". For example, you can't always take the least possible "next step" if the set of options is not well-ordered. And the axiom of choice allows you to chuck all that into a choice function which guides the way you choose the next step.
In the two examples that you brought up, the key difference is that in Rado graph we assume that the graph is countable. So we have a well-ordering of its vertices to give us the choice we need.
If Koenig's lemma is phrased as "Every countable tree ..." then you don't need the axiom of choice either, and if you formulate Rado graph as something which doesn't include explicitly countability (or can prove it directly), then the axiom of choice will also be needed. In particular one can arrange for a random graph which embeds every finite graph, whose cardinality is not well-orderable, and in fact Dedekind-finite.