Assume that G is a simple graph of order n, with n ≥ 4, and that for each vertex v of G, the deletion G − v is regular (that is, all vertices have the same degree). Prove that G is either the complete graph K_n or its complement.
This seems conceptually obvious, but i am struggling with how to form a proof. Say the degree of each vertex in G-v is k, then the degree of v must be k+1 as it connects to each vertex in G-v. So when v is deleted it decreases the degree of adjacent vertices by one. This means that G is k+1 regular. But how do I prove that this is the complete graph or its complement?