The maximum no. of edges in a DISCONNECTED simple graph...

Question

... on n vertices when it is not connected being equal to (1/2)(n - 1)(n - 2)...

I can see that for n = 1 & n = 2 that the graphs have no edges... however I don't understand how to derive this formula?

How to derive it using the handshake theorem?

Answer 1

Since the graph is not connected it has at least two components. Even if it has more than 2 components, you can think about it as having 2 "pieces", not necessarily connected.

Let $k$ and $n-k$ be the number of vertices in the two pieces. Then, each vertex in the first piece has degree at most $k-1$, therefore the number of edges in the first component is at most $\frac{k(k-1)}{2}$, while the number of edges in the second component is at most $\frac{(n-k)(n-k-1)}{2}$.

To finish the problem, just prove that for $1 \leq k \leq k-1$ we have $$\frac{k(k-1)}{2}+ \frac{(n-k)(n-k-1)}{2} \leq \frac{(n-1)(n-2)}{2}$$

You can also prove that you only get equality for $k=1$ or $k=n-1$.

Alternate solution There are exactly $k(n-k)$ edges between vertices in the two pieces.

If you add them to your graph, you get a simple graph, which by handshaking lemma, has at most $\frac{n(n-1)}{2}$ edges.

Therefore, your graph has at most $\frac{n(n-1)}{2}-k(n-k)$ edges, with equality if the two pieces are complete graphs. To maximize this number, you need to minimize $k(n-k)$ when $1 \leq k \leq n-1$. This is a quadratic function in $k$...

Answer 2

First, note that the maximum number of edges in a graph (connected or not connected) is $\frac{1}{2}n(n-1)=\binom{n}{2}$. This is because instead of counting edges, you can count all the possible pairs of vertices that could be its endpoints. That's the same as the maximum number of [unique] handshakes among $n$ people.

Now if a graph is not connected, it has at least two connected components. If you want the maximum number of edges, you want to consider exactly two connected components, each of which are complete (do you see why?). The last remaining question is how many vertices are in each component. We consider both "extremes" (the answer by N.S. formalizes this argument).

• If they have the same amount, you have $2\binom{n/2}{2}$ edges if $n$ is even, or $\binom{(n-1)/2}{2}+\binom{(n+1)/2}{2}$ if $n$ is odd.
• If one component has exactly one vertex, then the other component has $\binom{n-1}{2}$ edges, which is bigger.

Answer 3

Suppose we have 1 vertex on one side and other n-1 vertices on another side.To make it connected maximum possible edges(if consider it as complete graph) is $C^{n-1}_2$ which is $\frac{(n-1)(n-2)}{2}$.

Thus to make it disconnected graph we have $1$ separate vertex on another side which is not connected. Thus the maximum possible edges is $C^{n-1}_2$

Answer 4

Here's another way to derive that result, if you happen to know that for any (simple) graph $G,$ either the graph $G$ or its complement $\overline G$ is connected (see this question.) Let's assume $n\ge2$ so that the question makes sense; there is no disconnected graph on one vertex.

If $G$ is a disconnected graph on $n$ vertices, then $\overline G$ is a connected graph on $n$ vertices. A connected graph on $n$ vertices has at least $n-1$ edges, this minimum being attained when the graph is a tree. Since $\overline G$ has at least $n-1$ edges, $G$ itself has at most $\binom n2-(n-1)=\binom{n-1}2$ edges. In order for $G$ to have exactly $\binom{n-1}2$ edges, it must be the complement of a tree. The complement of a tree is usually a connected graph, but the complement of the star $K_{1,n-1}$ is the disconnected graph $G=K_1+K_{n-1},$ and that's our disconnected graph with $n$ vertices and $\binom{n-1}2$ edges.

Answer 5

Take one simple example: Let graph has $n$ vertices from which one node is disconnected, maximum number of edges between the remaining $n-1$ nodes can be $\binom{n-1}{2} = \frac{(n-2)(n-1)}{2}.$