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.
$\endgroup$ 31 Answer
$\begingroup$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.
(Proof sketch: start anywhere and keep walking, till you meet a vertex you've already seen (which will happen as there only finitely many): there are no dead ends as long as we meet new points because of the degree condition)).
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...
$\endgroup$
