Claim. A simple graph with 1212 vertices and 5656 edges must be connected.

Proof. Assume towards contradiction that GG is a simple disconnected graph on 1212 vertices with 5656 edges. This means the graph is a union of components, i.e. G=g1g2gk G=g_1\cup g_2\cup \cdots \cup g_k Where 2k122\le k\le 12.

Letting vk=V(gk)v_k=|V(g_k)|, we get that E(gk)i=1vk1i=vk(vk1)2 |E(g_k)|\le\sum_{i=1}^{v_k-1} i=\frac{v_k(v_k-1)}{2} Therefore E(G)i=1kvi(vi1)2=12i=1k(vi2vi)=12i=1kvi212i=1kvi \begin{align*} |E(G)|&\le\sum_{i=1}^{k}\frac{v_i(v_i-1)}{2} \\ &=\frac{1}{2}\sum_{i=1}^{k}\left(v_i^2-v_i\right) \\ &=\frac{1}{2}\sum_{i=1}^{k}v_i^2-\frac{1}{2}\sum_{i=1}^{k}v_i \\ \end{align*} The sum i=1kvi\sum_{i=1}^{k}v_i is the sum of all of the vertices, which is 1212. =12i=1kvi212(12)=12i=1kvi26 \begin{align*} &=\frac{1}{2}\sum_{i=1}^{k}v_i^2-\frac{1}{2}(12) \\ &=\frac{1}{2}\sum_{i=1}^{k}v_i^2-6 \\ \end{align*}

Letting vivjv_i\le v_j we get that vi2+vj2<vi2+vj2+2vj2vi+2=vi22vi+1+vj2+2vj+1=(vi1)2+(vj+1)2 \begin{align*} v_i^2+v_j^2&<v_i^2+v_j^2+2v_j-2v_i+2 \\ &=v_i^2-2v_i+1+v_j^2+2v_j+1 \\ &=(v_i-1)^2+(v_j+1)^2 \end{align*} 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)12i=12vi26=12[v12+v22]6=12[v12+(12v1)2]6 \begin{align*} |E(G)|&\le\frac{1}{2}\sum_{i=1}^{2}v_i^2-6 \\ &=\frac{1}{2}[v_1^2+v_2^2]-6 \\ &=\frac{1}{2}[v_1^2+(12-v_1)^2]-6 \\ \end{align*} Using previous logic this is maximized for v1=1v_1=1. E(G)12[12+(121)2]6=12[122]6=55 \begin{align*} |E(G)|&\le\frac{1}{2}[1^2+(12-1)^2]-6 \\ &=\frac{1}{2}[122]-6 \\ &=55 \\ \end{align*} In conclusion, E(G)55|E(G)|\le55, i.e. GG can have at most 5555 edges, which is a contradiction.