Give the minimum and maximum number of edges in an undirected connected graph of n vertices?

Question

will be the minimum (n-1) edges?

I'm not sure about the maximum

Answer 1

Yes .. The minimum number of edges for an undirected connected graph is (n-1) edges. To see this as the graph is connected, then there must be a unique path from each vertex to any other vertex, and removing any edge will make the graph disabled.

For the maximum number of edges (under the condition of simple graphs), each vertex is associated with all other vertices that occur with edges n(n-1)/2 (use the acknowledgment lemma). Another way: look at K_n (a full graph with n vertices) that has the maximum number of edges.

Answer 2

Claim: if there are N vertices, Min - N-1, and max - N * (N-1) / 2

Evidence:

Consider the adjacency matrix, where the elements are either 1 (to indicate the presence of an edge) or 0 (to indicate the absence of an edge). In order for the graph to be connected, at least one "1" must be in each row of the upper triangle.

the minimum is achieved only by placing one in each line of the upper triangle. Now, if the adjacency matrix is ​​N by N, the first row has N-1 elements in the upper triangle, the second has N-2 elements in the upper triangle, ... and the last row has 0 elements in the upper triangle. That is, there are N-1 complete lines with an "upper triangle", each of which has only one 1. Therefore, the number of edges in N-1.

the maximum occurs if each element of the upper triangle has one. Now the number of elements in the upper triangle of the entire matrix is

1 + 2 + ... + (N-2) + (N-1) = N * (N-1) / 2.

For the last equality, we call the finite sums of calculus courses. See the second formula here and replace "m" with (N-1) ": https://en.wikipedia.org/wiki/List_of_mathematical_series#Sums_of_powers

PS: I'm sorry that I can not use LaTeX on SO!