Give the minimum and the maximum numbers of edges in an undirected connected gra

Question

Give the minimum and the maximum numbers of edges in an undirected connected graph of n vertices. Justify your results. Give an efficient greedy algorithm that detects whether there is a cycle in a given undirected connected graph. Give and justify its time and memory complexity. Give an efficient greedy algorithm that detects whether there is a cycle in a given linked list (where each element t has at most one following element next(i)) and where elements are comparable. Give and justify its time and memory complexity.

Explanation / Answer

The minimum number of edges for undirected connected graph is (n-1) edges.
To see this, since the graph is connected then there must be a unique path from every vertex to every other vertex and removing any edge will make the graph disconnected.
The maximum number of edges (assuming simple graphs), every vertex is connected to all other vertices which gives arise for n(n-1)/2 edges (use handshaking lemma).

Another way: look over K_n (the complete graph with n vertices) which has the maximum number of edges.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.