I'm trying to prove something about graph theory, but I'm not sure if I'm thinking in the right direction.
Let $G$ be a simple graph, that is a graph without multiple edges and loops, let $n$ be the number of nodes of $G$ and $E$ the number of edges. Let $k$ be the number of components of $G$, then $E \leq \frac{(n-k+1) \cdot (n-k)}{2}$
I ""get"" why this must be the case, it has to do with the fact that $E \leq \frac{(n-1) \cdot n}{2}$ for all simple graphs (the simple graph with $n$ nodes with the most amount of edges is a complete graph). So I tried building an induction proof around this idea, with induction on k.
For $k = 1$ this statement is obvious, because as said earlier the simple graph with $n$ nodes with the most amount of edges is a complete graph.
Let $k \in \mathbb{N}$ be randomly given,suppose the statement holds for all $l \in \mathbb{N}$ so that $l \leq k$ Is the stament true for $k+1$?
Let $G_{1}$ be a simple graph with $k_{1}$ components, $n_{1}$ nodes and $E_{1}$ edges . By the induction hypothesis we find that $E_{1} \leq \frac{(n_{1}-k_{1}+1) \cdot (n_{1}-k_{1})}{2}$
Out of $G_{1}$ we can build a graph $G$ with $k+1$ components. Let this new component be a simple graph with $k_{2}$ components, $n_{2}$ nodes and $E_{2}$ edges. Again we find that $E_{2} \leq \frac{(n_{2}-1) \cdot n_{2}}{2}$.
Now we construct the graph $G$ by adding this last component to the graph $G_{1}$ and connecting all the $n_{2}$ nodes with the $n_{1}$ nodes. $G$ now has $n_{1}+n_{2}$ nodes and at most $n_{1} \cdot n_{2} + \frac{(n_{1}-k+1) \cdot (n_{1}-k)}{2} + \frac{(n_{2} -1)\cdot n_{2}}{2}$ edges.
And now I'm stuck.Am i thinking in the right direction or am I not even close? Any hints and other help would be welcome!
You can do it this way, but you need to get your induction sorted out a bit, and the computational details still seem to be a bit messy (though I may just be doing things the hard way). Assume that the result is true for simple graphs with at most $k$ components, and let $G$ be a simple graph with $k+1$ components. Let $C$ be one of the components of $G$, and let $G_1=G-C$. Let $n_C$ be the number of nodes of $C$, and $E_C$ the number of edges. Similarly, let $n_1$ be the number of nodes of $G_1$ and $E_1$ the number of edges. The induction hypothesis tells you that
$$E_1\le\frac{(n_1-k+1)(n_1-k)}2$$
and
$$E_C\le\frac{n_C(n_C-1)}2\;,$$
so
$$\begin{align*} E&=E_1+E_C\le\frac{(n_1-k+1)(n_1-k)}2+\frac{n_C(n_C-1)}2\\ &=\frac12\big((n_1-k+1)(n_1-k)+n_C(n_C-1)\big)\;. \end{align*}$$
Thus, we’d like to show that
$$\begin{align*} (n_1-k+1)(n_1-k)+n_C(n_C-1)&\le\big(n-(k+1)+1\big)\big(n-(k+1)\big)\\ &=(n-k)(n-k-1)\\ &=n^2-2kn+k^2-n+k \end{align*}$$
Now
$$\begin{align*} (n_1-k+1)(n_1-k)+n_C(n_C-1)&=n_1^2-2kn_1+k^2+n_1-k+n_C^2-n_C\\ &=\color{blue}{n_1^2+n_C^2}+k^2+n_1-2kn_1-n_C-k\\ &=\color{blue}{(n_1+n_C)^2-2n_1n_C}+k^2+n_1-2k(n-n_C)-n_C-k\\ &=n^2-2k(n-n_C)-n_C+k^2+n_1-k-2n_1n_C\\ &=n^2-2kn+k^2-n+k+2kn_C+2n_1-2k-2n_1n_C\;, \end{align*}$$
so we’d like to show that $2kn_C+2n_1-2k-2n_1n_C\le 0$, i.e., that $n_1n_C+k-n_1-kn_C\ge 0$. The lefthand side of this last inequality factors: group it as $n_1(n_C-1)+k(1-n_C)$, and you should have no trouble finding the factorization and proving that the product is non-negative. If you get stuck on that very last step, look at the hint in the spoiler-protected block:
There is another approach that does not use induction and involves less computation. Let $G$ be a simple graph with $k$ components, and let the $k$ components of $G$ be $C_1,\ldots,C_k$. For $i=1,\ldots,k$ let $n_i$ be the number of nodes of $C_i$, and let $E_i$ be the number of edges of $C_i$. You know that
$$E_i\le\frac{n_i(n_i-1)}2\;,$$
so
$$E=\sum_{i=1}^kE_i\le\frac12\sum_{i=1}^kn_i(n_i-1)=\frac12\left(\sum_{i=1}^kn_i^2-\sum_{i=1}^kn_i\right)=\frac12\left(\sum_{i=1}^kn_i^2-n\right)\;.$$
Thus, you’d like to show that
$$\sum_{i=1}^kn_i^2-n\le(n-k+1)(n-k)$$
or, equivalently, that
$$\sum_{i=1}^kn_i^2\le(n-k+1)(n-k)+n\;.\tag{1}$$
This follows from the fact that $\sum_{i=1}^kn_i^2$ is maximized when $k-1$ of the components have one vertex each. This fact is not entirely trivial to prove, but the proof isn’t too hard. The trick is to show that if there are distinct $i$ and $j$ such that $1<n_i\le n_j$, replacing $n_i$ by $n_i-1$ and $n_j$ by $n_j+1$ increases $\sum_{i=1}^kn_i^2$. HINT: Compare $n_i^2+n_j^2$ with $(n_i-1)^2+(n_j+1)^2$.