1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.