I have just started my journey into the field of graph theory. I wish to show the following result:
Prove that for every disconnected graph $G = (V, E)$ it holds
$|E| \leq \frac{1}{2}
(|V| − 1)(|V | − 2)$.
I think the best way to tackle this, is via induction. I want to start with the smallest possible graph you can have, which would be on $2$ vertices, so $n=2$
We know that there are $0$ edges and thus:
$$|E|=0 \leq \frac{1}{2} (2-1)(2-2)=0. $$
So our base case holds. Now the difficulty would be to assume we have some arbitrary graph for which this formula holds, to then prove it holds for all graphs bigger than this. I cannot possibly construct all bigger graphs. I am guessing there is some different strategy in graph theory to induction proofs.
This result could also follow easily from the handshaking lemma if I assume that $n-1$ vertices have at most degree $n-2$. If someone has an alternative suggestion, please let me know.
Best Answer
Hint: It might be easier to not use induction.
Suppose $G = (V,E)$ is a disconnected graph. Then, we can split $G$ into two disconnected subgraphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ with $|V_1| \ge 1$, $|V_2| \ge 1$.
Trivially, $|V| = |V_1|+|V_2|$ and $|E| = |E_1|+|E_2|$.
Also, $|E_1| \le \dbinom{|V_1|}{2}$ and $|E_2| \le \dbinom{|V_2|}{2} = \dbinom{|V|-|V_1|}{2}$.
Can you use the above to show that $|E| = |E_1|+|E_2| \le \dbinom{|V|-1}{2}$?