Proof by contradiction:
Let G be a simple graph on n ≥ 4 vertices. Prove that if the
shortest cycle in G has length 4, then G contains at most one
vertex of degree n −1.