How many edges a graph with 500 vertices and 19 components has?

260 Views Asked by At

$G$ is a graph with no cycles, 500 vertices, and 19 connected components. How many edges it has? any help/hint?

1

There are 1 best solutions below

3
On BEST ANSWER

Each component is connected and does not contain circuits. Thus, each component is a tree. A tree with $n$ vertices has $n-1$ edges. Thus, the total number of edges is$$\sum_{i=1}^{19}(n_i-1)=500-19=481$$where $n_i$ is the number of vertices in the $i^{th}$ component.