Question

Finish the proof of the case when \(a \ne b\) in Lemma 1.

Short answer

Thus, \(m < n \Rightarrow m \le n - 1\).

Step-by-step solution

Given data

The given data is \(a \ne b\).

 Step 2: Concept used of pigeonhole principle

The pigeonhole principle states that if\(n\)items are put into\(m\)containers, with\(n > m\), then at least one container must contain more than one item.

Find the proof

Suppose there is a path from a to\({\rm{b}}\) in \({\rm{R}}\) where \(a \ne b\).

Let \(m\) be the length of shortest such path.

Suppose \({x_0} = a,{x_1},{x_2}, \ldots ,{x_m} = b\) is such that a path.

As \(a \ne b\), by the minimality of \(m,b \ne {x_i}\) for any \(i\)

If \(m \ge n\) by the Pigeonhole principle at least two of \({x_0},{x_1},{x_2}, \ldots ,{x_{m - 1}}\) are identical since there are only \(|A\backslash \{ b\} | = n - 1\) choices for them.

Suppose \({x_i} = {x_j}\) where \(i \ne j\).

Omitting the circuit still leaves us a path from a to b of length shorter than \({\rm{m}}\), contradicting its minimality.

Thus, \(m < n \Rightarrow m \le n - 1\).