# Finding min and max number of edges of a connected graph

• Apr 27th 2011, 12:38 PM
xEnOn
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. (Sweating)

Thanks.
• Apr 27th 2011, 02:27 PM
Plato
Quote:

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 $\mathcal{K}_{20}$ give a maximum?
• Apr 28th 2011, 02:02 AM
xEnOn
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?
• Apr 28th 2011, 02:10 AM
Matt Westwood
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.
• Apr 28th 2011, 02:32 AM
xEnOn
Then the maximum number of edges for a graph of 20 vertices could be $20!$ ?
Like Vertex A could join Vertex B, could also join Vertex C and form a complete graph?