[Math] Prove that the maximum connected components in a graph is $V+1-\left\lceil\frac{1+\sqrt{1+8E}}{2}\right\rceil$

graph theory

Prove that the maximum connected components in a graph is $V+1-\left\lceil\frac{1+\sqrt{1+8E}}{2}\right\rceil$

I came up with this intuitively but was not able to prove it. The idea is that a graph with the maximum number of connected components would have individual nodes and 1 clique connected with at most one other node.

The derivation is to find an order n of a subset of V such that $\binom{n}{2}=E$, meaning that $n^2-n-2E=0$

Edit: We are given V number of vertices and E number of edges and solving for maximum number of connected components

Best Answer

Hint: You may assume that each connected component is a complete graph. This only decreases your bound, hence it is still a maximum.

Edit: Observe that if $E^* \geq E$, then $\lceil \frac{ 1 + \sqrt{1+8E^*}}{2} \rceil \geq \lceil \frac{ 1 + \sqrt{1+8E}}{2} \rceil$. Hence, if we increase the number of edges and the bound still holds, then

we know that the bound is true in the initial case.

Hint: Apply the convexity of ${ n \choose 2 }$, to further increase the total number of edges, given that there are $k$ connected components.

Edit: Assume that you have connected components of size $n_1, n_2, \ldots n_k$. Then since they are a complete graph, there are $ E = {n_1 \choose 2} + { n_2 \choose 2} + \ldots {n_k \choose 2} $ edges. By convexity, we know that $E \geq k { \frac{V}{k} \choose 2} = E^* $. It remains to verify that

$$ k \leq V+1 - \lceil \frac{ 1 + \sqrt{1+8E^*}}{2} \rceil $$

Related Solutions

[Math] How to use BFS or DFS to determine the connectivity in a non-connected graph

Your solution looks good to me!

I have one suggestion if you consider directed graphs. Consider the graph:

A -> B -> C
D -> F

Let's say your algorithm starts arbitrarily at node B. It will traverse the graph through B and C and mark them as connected components - but it won't catch A!

A simple way to solve this problem is to allow the DFS to traverse the graph going both forwards and backwards, as though the graph was non-directed.

This is another way to solve it: Your algorithm produces sets of connected components. Let's say, as above, that the algorithm starts at B and produces the set {B, C}. Then, let's say that the algorithm arbitrarily selects A as its next starting point. When it traverses the graph to B, it should union the new set of connected components {A} with the already-existing set {B, C} instead of simply skipping node B.

In general, if you encounter a node that's already part of a group of connected components during a DFS, mark the set of connected components that the node is in and then skip the node. Then, when you've finished traversing as many nodes as possible without retracing paths found by previous DFS's, union all of the marked sets and the set produced by the most recent DFS into one set of connected components and discard the unioned sets.

[Math] Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

Let $a_1, \dotsc, a_6$ be the number of vertices of the components. We know that $a_i \geq 1$ and $\sum a_i = 25$.

To find the minimum number of edges of $G$, let's first look at a single connected component. A component with $n$ vertices cannot have less than $n-1$ edges. Also, a star graph is connected and have exactly $n-1$ edges, so we can attain this minimum.

Thus, the minimum number of edges in $G$ will be: $$ \sum_{i=1}^6 (a_i - 1) = \sum_{i=1}^6a_i - 6 = 25 - 6 = 19 $$

The maximum can be found in a similar way. The maximum number of edges in a component with $n$ vertices is $\binom{n}{2}$, that is attained on a complete graph $K_n$. Thus we want to maximize: $$ \sum_{i=1}^6\binom{a_i}{2} = \sum_{i=1}^6 \frac{a_i(a_i-1)}{2} = \frac{1}{2} \left( \sum_{i=1}^6 a_i^2 - \sum_{i=1}^6a_i \right)$$ $$ = \frac{1}{2} \left( \sum_{i=1}^6 a_i^2 - 25 \right)$$

Note that $\sum_{i=1}^6a_i^2$ is convex, so the maximum is attained on the boundary of the region given by $\sum_{i=1}^6a_i = 25$, so we have a maximum when $a_1 = 1$, $a_2 = 1$, $a_3 = 1$, $a_4 = 1$, $a_5 = 1$ and $a_6 = 20$. Hence the maximum number of edges is: $$ \frac{1}{2} \left( 20^2 + 5 - 25 \right) = 190$$ That is attained when the components are five copies of $K_1$ and one $K_{20}$.

Best Answer

Related Solutions

[Math] How to use BFS or DFS to determine the connectivity in a non-connected graph

[Math] Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

Related Question