Let G be a simple undirected graph with n (n > 10) vertices and k connected components. What is the minimum possible number of edges of G?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. n − k
Explanation
Each component with nᵢ vertices needs at least nᵢ − 1 edges (a tree). Σ(nᵢ − 1) = n − k.More Discrete Structures and Optimization questions
- The negation of "Some students like hockey" is:
- A relation R is defined on ordered pairs of integers as (x, y) R (u, v) if x < u and y > v. Then R is
- Suppose you are married and you and your partner attend a party with three other married couples. Several handshakes took place. No one sho…
- Consider the following graph with vertices A, B, C, D and edges: A – B, B – C, A – D, B – D, C – D (A, B, C lie in a row; D is below and jo…
- Consider the following statements: P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges. Q: All vertices…
- Consider the following statements: A. There exists a Boolean algebra with 5 elements. B. Every element of a Boolean algebra has a unique co…