Thread: Finding min and max number of edges of a connected graph

A simple graph of 25 vertices and 6 connected components.
What is the minimum and maximum number of edges can the graph have?

Is there a formula to calculate the min and max? 25 vertices is too huge to draw and there are several possibilities for minimum number as well as maximum number of edges.

Thanks.

Originally Posted by xEnOn

A simple graph of 25 vertices and 6 connected components. What is the minimum and maximum number of edges can the graph have?

A single vertex is a degenerate component. Think of five degenerate components and one with twenty vertices.
If the one with twenty vertices is tree, does that give a minimum?
Does give a maximum?

ohh...a graph has minimum edges when it is a tree. So Edges = 20-1 = 19, is the minimum number of edges.

But for the maximum, how I can calculate the maximum edges when there are 20 vertices? It can have infinite number of edges wouldn't it?

A simple graph (which I presume this is or the q won't make sense) allows only one edge per vertex pair, and no loops.

Then the maximum number of edges for a graph of 20 vertices could be ?
Like Vertex A could join Vertex B, could also join Vertex C and form a complete graph?