How do I find the number of maximum possible number of connected components of a graph with given the number of vertices and edges.

Question

The specific question I am trying to solve is to find the maximum number of connected components in a graph with 14 vertices and 44 edges.

My strategy is to make a complete graph as close as possible to the number of edges so as to quickly exhaust the number of edges and the left vertices can be individual independent sets. But can't seem to get the right answer with the technique.

Is there a specific formula or steps to do this problem

Answer 1

The number of edges in a complete graph with $v$ vertices is

$\frac{v^2-v}{2}$

You want to use as many edges as possible to a group of vertices. Given a graph $G$ with $e$ edges and $v$ vertices. We want to choose the smallest integral $n$ to satisfy the following inequality to fit as many vertices into the connected component.

$e \le \frac{n^2-n}{2}$

This leaves you with $v - n$ vertices with $0$ edges plus an additional component which has $n$ vertices connected.

# of connected components $ = v - n + 1$

For a graph with $v = 14$ and $e = 44$. You can see that the smallest integral $n$ to satisfy this equation is $10$

$44 \le \frac{10^2-10}{2}$

This graph has $14-10+1 = 5$ connected components