# Proving a result about a graph with $p$ connected components

I am trying to prove the following result: let $$G=(V,A)$$ be a graph with $$p$$ connected components. Prove that

$$|V|-p\leq |A|\leq \binom{|V|-p+1}{2}$$

I have shown that if $$G$$ is a connected graph with $$n$$ vertices and $$m$$ edges, then $$m\geq n-1$$.

What I have tried to do is: as we have shown above, $$|A|\geq |V|-1$$, as there is at least one connected component (the graph $$G$$ itself), $$|V|-p$$ will also be true!

$$\binom{|V|-p+1}{2}=\textrm{ number of edges of the graph } K_{|V|-p+1}$$

$$|V|-p\leq |A|$$

It is clear that at most, $$\binom{|V|-p+1}{2}$$ can be equal to $$\binom{n}{2}=m(K_n)$$ since there is at least one connected component, the graph $$G$$ itself.

I don't know how to continue.

• As stated, your first proof is invalid: you have applied a result whose hypothesis is "$G$ is a connected graph" to a graph that is not necessarily connected. (The fact that $G$ has a connected component isn't sufficient to satisfy that hypothesis.) Indeed, if that proof were correct, then you would have proved that $\#A\ge\#V-1$ for any graph, but that's definitely false—consider a graph with no edges for example. Instead, try thinking about the proof of that result and how it can be modified for non-connected graphs. Mar 14 '21 at 19:19

HINT: You know that $$|A|\ge|V|-1$$ for a connected graph, but you cannot apply that result to $$G$$ here unless $$p=1$$, so that $$G$$ is connected. You can, however, prove the first inequality by applying that result to each of the $$p$$ components of $$G$$.
You know that $$\binom{|V|-p+1}2$$ is the number of edges in $$K_{|V|-p+1}$$, but that graph is not $$G$$ (unless $$p-1$$). In order to apply that result here, you will have to prove that $$G$$ cannot have any more edges than the graph $$K_{|V|-p+1}$$ has. If you add $$p-1$$ isolated vertices to $$K_{|V|-p+1}$$, you get a graph $$G_0$$ with $$|V|$$ vertices and $$p$$ connected components. You can prove the second inequality by showing that among all graphs with $$|V|$$ vertices and $$p$$ connected components, $$G_0$$ is the one with the largest number of edges; I’ll sketch one way to do.
Let $$G$$ be any graph with $$|V|$$ vertices and $$p\ge 2$$ connected components. Let $$C_1$$ and $$C_2$$ be two of the components of $$G$$, with $$n_1$$ and $$n_2$$ vertices, respectively; $$C_1$$ and $$C_2$$ have altogether at most $$\binom{n_1}2+\binom{n_2}2$$ edges. (Why?) Replace $$C_1$$ by an isolated vertex and $$C_2$$ by $$K_{n_1+n_2-1}$$, and show that the resulting graph has at least as many edges as $$G$$ and still has $$|V|$$ vertices and $$p$$ components. Show that by performing this operation a finite number of times you can convert $$G$$ to $$G_0$$, and conclude that $$G$$ has at most as many edges as $$G_0$$.