1. The problem statement, all variables and given/known data Prove that all vertices of a complete graph Kn have deg(v) = (n-1) 2. Relevant equations ∑ deg(v) = 2|E| |E| = ½(n)(n-1) for Kn 3. The attempt at a solution I may have over thought this but this was my initial path at a formal proof. Using the degree sum formula above and the formula for |E| for Kn, ∑ deg(v) = 2|E| = n(n-1) Kn has n vertices so, deg(v1) + deg(v2) + . . . . + deg(vn) (1/n) = (n-1) ∴ Each vertex , v, has degree (n-1) EDIT: The degree sum formula was mistakenly labeled as the Handshaking lemma.