## Problem1B

Problem1b: Suppose ${G}$ is a simple graph on ${10}$ vertices that is not connected. Prove that ${G}$ has at most ${36}$ edges. Can equality occur?

Solution: Suppose ${G}$ has ${k}$ connected components, where ${ k\geqslant 2.}$ We can always find a graph ${G^{\prime }}$ with ${k-1}$ components by adding an edge connecting two of the ${k}$ components of ${G,}$ and ${G^{\prime }}$ has more edges than ${G.}$ Hence to maximize the number of edges of ${G}$ which is not connected, we must have ${k=2.}$ Suppose ${G}$ is a disjoint union of two connected components ${G_{1}}$ and ${G_{2},}$ and ${ |V(G_{1})|=m,\ |V(G_{2})|=n-m.}$ To maximize the number of edges, we only need let ${G_{1},G_{2}}$ be the complete graphs. Hence the total number of edges of ${G}$ is ${\binom{m}{2}+\binom{n-m}{2}=-m(n-m)+\frac{n^{2}-n}{2}.}$ To maximize the number, we can either choose ${m=1}$ or ${m=n-1,}$ both lead to the same result ${\frac{(n-1)(n-2)}{2}.}$ When ${n=10,}$ then the graph ${G}$ has at most ${\frac{(10-1)(9-1)}{2}}=36$ 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.