Proving path length, transitive closure Set A is finite with n elements. Suppose a and b are elements of a set A with a != b. Let R be a relation on the set A so that there is a path from a to b of length at least 1. Show there is a path from a to b of length not exceeding n − 1.
I understand the proof for when a does equal b. And though I understand conceptually how this proof works, I am unable to put it in words.
 A: I will try to explain using less formal language.
Assume there is a path at least one in relation $R$ on Set $A$ from $a$ to $b$. Let $m$ be the shortest length of such path, so $x_0,x_1,x_2,...,x_{m-1},x_m$ is the path where $x_0 = a$ and $x_m = b$.
In the case when $a = b$, suppose $m > n$, we have $n$ vertices in total in the set $A$, so among the $m$ vertices $x_0,x_1,x_2,...,x_{m-1}$, there will be at least two vertices that are equal, according to the pigeonhole principle.
If two vertices are equal, then there will be a loop in the path and we can get rid of the loop to obtain the shortest path, so there will be at least $n$ path (i.e., $m = n$).
In the case when $a \not = b$, among the $m$ vertices $x_0,x_1,x_2,...,x_{m-1}$, no vertices can be equivalent to $b$, otherwise $m$ will not be the shortest path from $a$ to $b$. So there will be $n-1$ choices of vertices for the $m$ vertices. If $m > n - 1$, then by the pigeonhole principle, at least two vertices will be the same. Then if two vertices are equal, we can again get rid of the loop and obtain the shortest path, so there will be at least $n-1$ path.
A: Let $P_0 = \{a\}$, and let $P_{k+1} = P_k \cup \{x | \, yRx \text{ for some } y \in P_k \}$. $P_k$ is the set of elements reachable in $k$ or fewer steps
starting from $a$.
Note that $P_k \subset P_{k+1}$ and $P_k \subset A$ for all $k$, hence
$|P_0| \le |P_k| \le |P_{k+1}| \le |A|$.
Hence there is some $m$ such that $|P_0| < |P_2| < \cdots < |P_m|$ are strictly nested, and $P_{k+1} = P_k$ for all $k \ge m$. It follows from
this that $m \le n-1$.
Since there is a path from $a$ to $b$, we must have $b \in P_l$ for some $l$.
If $l \le n-1$ then we have the desired result. If $l > n-1$, we note that
$P_l = P_m$, and hence there is a path from $a$ to $b$ of length $\le m \le n-1$.
