Question: Consider a simple graph G with n vertices. What is the minimum number of edges that G must have in order to ensure that it is connected? Justify your answer.
My attempt: Let G = $(V, E)$. Consider a vertex $v \in E$. If G is connected, it is necessary that there is a path from $v$ to each of the remaining $n-1$ vertices. Suppose each path consists of a single edge. This adds up to a minimum of $n-1$ edges. Since $v$ is now connected to every vertex, we see that there is a path between any two vertices $via$ $v$. Therefore G is connected and we are done. So a minimum of $n-1$ edges is required.
Is this a valid proof? Or am I missing something?
EDIT: Based on D Poole's answer, I should seek to maximize the expression $\binom{a}{2} + \binom{n-a}{2} + 1$, where $a$ and $n-a$ are the respective number of vertices in the two components.
Let $f(a) = \frac{a(a-1)}{2} + \frac{(n-a)(n-a-1)}{2} = \frac{2a^2 – 2na + n^2 – n}2$
$\frac{df}{da} = \frac{4a – 2n}2$.
Let $\frac{df}{da} = 0.$ Then $a = \frac n2$.
Applying the first derivative test we see that when $a = \frac n2$, $f(a)$ is maximum.
If n is even then there is no problem. If n is odd then should we take $\lfloor \frac n2 \rfloor$ or $\lceil \frac n2 \rceil$?
Best Answer
You show that you can have a graph with $n-1$ edges and be connected. I read the problem as finding the $m$ below: $$ m= \min\{M: \text{ if }G\text{ is a graph on }n \text{ vertices and }M \text{ edges, then }G \text{ is connected}\}. $$ Since there are graphs with $n-1$ edges with $n$ vertices that are NOT connected, $m$ should be larger.
EDIT: How to find this $m$?
A graph $G$ is connected if there is NOT a proper subset $A \subset V(G)$, $1 \leq |A| \leq n-1$ such that there are no edges between $A$ and $A^c$. In particular, for a connected graph $G$ and all subsets of vertices $A$ with $1 \leq |A| \leq n-1$, there is an edge between $A$ and $A^c$.
For a fixed subset $A$, how many edges can be present so that there are no edges between $A$ and $A^c$? We can have a complete graph on $A$ and a complete graph on $A^c$ but no edges between these two subgraphs. So we can have $${|A| \choose 2}+{n-|A| \choose 2}$$ potential edges in this disconnected graph. Conversely, if $G$ has at least $${|A| \choose 2}+{n-|A| \choose 2}+1$$ edges, then necessarily there is an edge between $A$ and $A^c$. Consequently, taking the maximum over all $|A|$, we have that $$ m = \max_a {a \choose 2}+{n-a \choose 2} +1. $$ When is this expression maximized?