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.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email