Question

What is the minimum number of cuts that a graph with ‘n’ vertices can have?

(a) n+1

(b) n(n-1)

(c) n(n+1)/2

(d) n(n-1)/2

This question was addressed to me in final exam.

This interesting question is from Minimum Cut topic in portion Minimum Cut of Data Structures & Algorithms II

Answer 1

The correct option is (c) n(n+1)/2

For explanation: The mathematical formula for a graph with ‘n’ vertices can at the most have n(n-1)/2 distinct vertices.