Every state may be reached in time at most $N-1$ in a finite state space 
Let $\{X_n\}$ be an irreducible Markov chain, with finite state space 
  $\mathbb{X}$ (of cardinality $N$). Prove that for $x_0\in \mathbb{X}$ the time $T_x=\inf\{k\geq 0:~X_k=x\}$ needed to reach a state $x\in \mathbb{X}$ is $\leq N-1$ (with positive probability).

Attempt. Since the chain is irreducible, for some (smallest) $n\in \mathbb{N}$ we have $p^{(n)}(x_0,x)>0$ and we have to show that $n\leq N-1$
(which would imply $T_x\leq N-1$). If $n\geq N$, then i don't seem to be able to get a contradiction. 
Thank you!
 A: From the definition of irreducibility, you are implicitly given a path $P_k$ with $P_0=x_0,P_m=x$ which has positive probability, but where perhaps $m>N-1$. Suppose it is. Then the path has more than $N$ points in it, so some point is repeated (this is just the pigeonhole principle). This cycle can be pruned out from $P_k$ to create a new, shorter path from $x_0$ to $x$ which also has positive probability.  Can you use this pruning procedure to finish the argument?
A: Following the hints given above by @Ian, for sake of completeness, I ll post a detailed answer: since $x_0,~x$ communicate, there is a path $x_0 \rightarrow x_1 \rightarrow \ldots \rightarrow x_m=x$ of positive probability that starts from $x_0$ and leads to $x_m=x$. 
Claim: there is a subpath $x_0=x_{k_0} \rightarrow x_{k_1} \rightarrow \ldots \rightarrow x_{k_\ell}=x$ such that $k_0=0 <k_1<\ldots<k_\ell\leq N-1$ (therefore $\ell\leq N-1$), such that states $x_{k_0},x_{k_1},\ldots,x_{k_\ell}$ are all distinct. Then, with positive probability, $T_x=\ell\leq N-1.$
Proof of claim: Let  $k_0=0 <k_1<\ldots<k_r$ be as desired. If 
$x_{k_r}=x$ then we are done, otherwise pic $k_{r+1}$ such that $x_{k_{r+1}}$ is the next state of the given path, distinct from $x_0,x_1,\ldots,x_{k_r}$. The procedure is finished in at most $N-1$ steps. 

Image: (an example) the path of 13 states may be reduced to a path of 8 states, leading with positive probability to $x$.
