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?
Obviously, G is regular. Denote the common degree in G by d. Claim that d is either n-1(n is the number of vertices of G) or 0, otherwise by deleting any vertex v, since some vertices are adjacent to v and others are not, these two group of vertices in G-{v} has different degrees, one is d and the other one is d-1. That’s a contradiction.