Graph Theory What is the minimum number of edges that a simp

Graph Theory

What is the minimum number of edges that a simple connected graph with n vertices can have?

Solution

The minimum no. of edges for a undirected connected graph is (n-1) since the graph is connected and 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 egdes that a simple graph can have with n vertices is [n(n-1)/2] as every vertex is connected to all other vertices.