Question: Question:

Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers.

We use an algorithm that loops through all the elements in the array, comparing Ai with Ai+1 to check if both are equal, where 0 <= i < n. If there exists some i, such that Ai+1 != Ai, the algorithm returns false. Otherwise, for all i, Ai = Ai+1, hence the algorithm outputs true.

Construct a graph G on n nodes where nodes i and j are adjacent iff the algorithm compares Ai and Aj. Since the algorithm makes n-1 comparisons, there are n-1 edges with n nodes in G, ehnce the graph is connected. With a connected graph, the algorithm will always return the correct ouput as for any i, j indices of the array, Ai and Aj will be directly (or indirectly) compared with each other. Making more than n-1 comparisons simply adds more edges to G, and does not change the fact that the graph is already connected with only n-1 edges, hence the output of the algorithm will not change.

Therefore, there is an algorithm described above that needs at most n-1 comparisons to check if n-element array contains all equal elements.

This is my attempt at a proof, but I am sure that the part on the graph being already connected is wrong. Can someone help me correct my proof?

Answer: 
How about considering [proof by induction](https://en.wikipedia.org/wiki/Mathematical_induction).

1. Given an array with 2 elements we make one comparison of those two elements, they are either the same or they aren't.
2. We assume that there exists an algorithm that that needs at most n-1 comparisons to check if n element array has all equal elements. So let's consider what happens with an n+1 element array. We can establish that the first n elements are identical (or not) by using at most n-1 comparisons and if they are identical we need one further comparison to check the n+1th element against any of the other n elements, thus we need at most n - 1 + 1 = n comparisons.
Let a sequence of $n$ elements. If all pairs of consecutive elements are equal, then by transitivity all elements are equal. By contradiction, if they are not all equal, then there is certainly a pair of consecutive elements that differ.

Hence

$$\bigwedge\_{i=0}^{n-1} (A\_i=A\_{i+1})$$ settles the query, in $n-1$ comparisons. This proves the *existence* claim.

On another hand, a binary relation (such as equality) can only reduce by one the number of equivalence classes. This proves *optimality* of $n-1$.