What is the role of induction in the proof of König's Lemma? I am looking at this version of König's Lemma: let $T$ be a tree with countably infinite nodes, and each node has finite degree. Then, $T$ has a simple path containing countably infinite number of nodes.
From what I understand, we can let $S$ be the set of all nodes with infinite descendants. $S$ is nonempty since the root node is in it. Furthermore, we can define a relation $R$ such that $xRy \implies y$ is a child of $x$. Let $a \in S$, then since $a$ has infinite descendants, there must be a $b \in S$ such that $a Rb$. So, this relation is total or entire.
We can then apply the axiom of dependent choice on $S$ to get a sequence of nodes $(x_n)$, such that $x_n R x_{n+1}$. This sequence is the simple path required for the lemma.
However, I have read several proofs that use induction. Don't these proofs also require the axiom of dependent choice? If so, why are we using induction, which gives a simple path of length $n$, for all $n \in \mathbb{N}$, instead of directly defining the relation like I did above?

There are two points here.

*

*Induction and dependent choice work hand by hand. Dependent choice is exactly the choice mechanism which allows to pass from "for every finite $n$ there is an extension", which we can usually show using induction, to a coherent infinite sequence.
Meaning if you prove something like "If $x_n$ is chosen, choose $x_{n+1}$ as such and such" then the guarantee that the entire sequence $\{x_n\mid n\in\Bbb N\}$ even exists is due to Dependent Choice.


*If the underlying set can be well-ordered. For example, it is $\Bbb N$, then one can actually use induction to define the sequence, and no appeal to the axiom of choice is needed, because the induction process chooses the points of the sequence uniformly.
(I should also point out that compactness arguments also require a bit of the axiom of choice in their general settings.)
