$G$ is a graph with no cycles, 500 vertices, and 19 connected components. How many edges it has?
any help/hint?
How many edges a graph with 500 vertices and 19 components has
discrete mathematicsgraph theory
discrete mathematicsgraph theory
$G$ is a graph with no cycles, 500 vertices, and 19 connected components. How many edges it has?
any help/hint?
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.