For an undirected graph GGG with 30 vertices and 4 connected components, the minimum number of edges occurs when each connected component is minimally connected (i.e., each component is a tree).
- A connected component with viv_ivi vertices has at least vi−1v_i-1vi−1 edges.
- If the graph has k=4k=4k=4 components with vertex counts v1,v2,v3,v4v_1,v_2,v_3,v_4v1,v2,v3,v4 such that v1+v2+v3+v4=30v_1+v_2+v_3+v_4=30v1+v2+v3+v4=30,
- The minimum total number of edges is:
(v1−1)+(v2−1)+(v3−1)+(v4−1)=(v1+v2+v3+v4)−4=30−4=26(v_1-1)+(v_2-1)+(v_3-1)+(v_4-1)=(v_1+v_2+v_3+v_4)-4=30-4=26(v1−1)+(v2−1)+(v3−1)+(v4−1)=(v1+v2+v3+v4)−4=30−4=26
This minimum is independent of how the vertices are distributed among the components because the sum of vertices is fixed and each component must have at least one vertex. Hence, the minimum number of edges is: 26 edges
Explanation
- Each connected component must have at least vi−1v_i-1vi−1 edges to be connected.
- Summing over all 4 components, the minimum total edges is total vertices minus the number of components.
- This is a general formula: for a graph with nnn vertices and kkk connected components, minimum edges = n−kn-kn−k.
Thus, for n=30n=30n=30 and k=4k=4k=4, minimum edges = 30−4=2630-4=2630−4=26.
