0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In your base case, you meant (2-2) instead of (2-0) right? $\endgroup$ – mathpadawan Nov 20 '18 at 2:35
  • $\begingroup$ yes indeed, you are correct. $\endgroup$ – Wesley Strik Nov 20 '18 at 6:13
1
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ By $\binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices. $\endgroup$ – Wesley Strik Nov 19 '18 at 19:37
1
$\begingroup$

Say part one has $x$ vertices and other $n-x$. Then we have at most $${x\choose 2}+{n-x\choose 2}$$ edges, which is clearly $$\leq {n-1\choose 2}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.