>>11318083For a graph G with n vertices, if a vertex a has degree k, then the connected component it's in needs to have at least k+1 vertices. For another vertex b, if it has degree larger than n-k-1, then it's connected component needs to have more than n-k vertices.

Assuming a and b are on distinct connected components, you have n>k+1+n-k=n+1, and thus a and b are in the same component, by contradiction. If all vertices other than a have degree larger than n-k-1, then all vertices are on the same connected component as a, and the graph is connected.

>>11318674Lewd.

>>11319744Set . Then the new LHS for the induction becomes .