**Problem1b: Suppose **** is a simple graph on **** vertices that is not connected. Prove that **** has at most ** ** edges. Can equality occur?**

**Solution:** Suppose has connected components, where We can always find a graph with components by adding an edge connecting two of the components of and has more edges than Hence to maximize the number of edges of which is not connected, we must have Suppose is a disjoint union of two connected components and and To maximize the number of edges, we only need let be the complete graphs. Hence the total number of edges of is To maximize the number, we can either choose or both lead to the same result When then the graph has at most edges, and equality can occur.

**Notes: **I searched the key “maximal number of edges” in our library maths database, and found many papers, some of them were published on top journals! It might be interesting to make a survey of problems on this type.