Proof.
Assume towards contradiction that G is a simple disconnected graph on 12 vertices with 56 edges.
This means the graph is a union of components, i.e.
G=g1∪g2∪⋯∪gk
Where 2≤k≤12.
Letting vk=∣V(gk)∣, we get that
∣E(gk)∣≤i=1∑vk−1i=2vk(vk−1)
Therefore
∣E(G)∣≤i=1∑k2vi(vi−1)=21i=1∑k(vi2−vi)=21i=1∑kvi2−21i=1∑kvi
The sum ∑i=1kvi is the sum of all of the vertices, which is 12.
=21i=1∑kvi2−21(12)=21i=1∑kvi2−6
Letting vi≤vj we get that
vi2+vj2<vi2+vj2+2vj−2vi+2=vi2−2vi+1+vj2+2vj+1=(vi−1)2+(vj+1)2
This shows that in order to maximize the sum we should move the vertices into
the larger components, even to the point of deleting smaller components.
This leads us to the following.
∣E(G)∣≤21i=1∑2vi2−6=21[v12+v22]−6=21[v12+(12−v1)2]−6
Using previous logic this is maximized for v1=1.
∣E(G)∣≤21[12+(12−1)2]−6=21[122]−6=55
In conclusion, ∣E(G)∣≤55, i.e. G can have at most 55 edges, which is a contradiction.
□