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?