0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 14 '21 at 19:19
2
$\begingroup$

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$.

$\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.