Question

1. Among all simple graphs with 20 vertices, determine (with justification) the minimum possible and the maximum possible number of edges such a graph could have.

Answer 1

Answer:

Minimum possible edges is 19,

Maximum possible edges is 190.

Step-by-step explanation:

∵ When n vertices is joined by edges,

The minimum number of edges = n - 1 ( i.e. they are making a unique path in which first and last vertex are joined with only one vertex while the other vertices are joined with two vertices only )

Also, if the number of edges < n - 1 then the graph would be disconnected ,

While, the maximum number of edges = $\frac{n(n-1)}{2}$ ( i.e. every vertex is joined with every vertex )

Here, n = 20,

So, the minimum possible edges = 20 - 1 = 19,

And, maximum possible edges = $\frac{20(20-1)}{2}$

= $\frac{20\times 19}{2}$

= 10 × 19

= 190