# Simple connected graph question

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

A simple graph means that there is only one edge between any two vertices, and a connected graph means that there is a path between any two vertices in the graph. So wouldn't the minimum number of edges be n-1? This would form a line linking all vertices.

Am I missing something? This seems too easy.

• That is correct. A formalization of your reasoning can be done using induction. – Fimpellizieri Apr 27 '16 at 4:27
• Yes it's easy but you do not really have a proof. Show that adding an edge reduces the number of components by at most $1$. So if you begin with $n$ isolated vertices, you have to add at least $n-1$ edges to get exactly $1$ component. – Forever Mozart Apr 27 '16 at 4:29
• "Simple" is irrelevant. If the graph has the minimum number of edges for connectivity, it won't have two vertices joined by two edges. – bof Apr 27 '16 at 4:48

Fact: if the degree of all points is 2 or more, there is a cycle $v_1 \rightarrow v_2 \rightarrow \ldots v_1$ in the graph.
This sets you up for induction: assume it's true for $n$ ($n=1$ is trivial), then take a minimally connected graph of size $n+1$. If all degrees are $2$ or more, we have a cycle, and we can remove an edge from the cycle and keep connectedness of the total graph, contradicting minimality. So we have a point of degree $1$ (degree $0$ cannot happen in a connected graph), and we remove this 1 edge and 1 vertex and apply the induction assumption...