9 Use the corollary on page 4 of notes for Chapter 2 to prov

9. Use the corollary on page 4 of notes for Chapter #2 to prove that (Kn)=n-1 Corollay: Ang simple gnph With n Vortice ar n-1110-2 Mant An-21 adge 1) Connected

Solution

Consider the highest number of edges a graph can have without being connected. It must have two connected components, and, to maximize the number of edges, they must be size (n 1) and 1. To maximize the edges, the large component must be a complete graph, which will have (n 1)(n 2)/2 edges.