The number of edges disconnected graphs
Task number: 4041
Determine the minimum and maximum number of edges for a graph on \(n\) vertices with \(c\) components.
Solution
The smallest number of edges has a graph, where each component does not contain a cycle, and therefore is a tree. Such graph has \( n-c \) edges.
Most edges has a graph, where each component is a complete graph. The maximum is reached if \( c-1 \) components are single-points and one has \( n-c-1 \) vertices.
Answer
A graph with \(c\) components has at least \(n-c\) and at most \(\binom{n-c+1}{2}\) edges.
