# Proof for connected Graph

Trying to solve this proof: proof any undirected loop-free graph on n vertices with at least (n-1)(n-2)/2 + 1 edges is connected. Give an example of a disconnected n-vertex graph with one fewer edge

I am not sure how to solve this one, I know that graphs with (n-1)(n-2)/2 edges are connected and then have assumed adding one edge would also leave this graph connected. When i prove by contradiction i end up with a disconnected graph unable to have k + 1 vertices and at least k(k-1)/2 + 1 edges, but feel that this is incorrect.

How to prove this and how to give an example with one fewer edge?

• What do you mean by loop-free graph? Do you mean a forest? – Crostul Nov 27 '16 at 23:38
• I guess you are also assuming that $G$ is a simple graph, i.e., any two vertices are joined by at most one edge? Otherwise, a disconnected graph on three vertices can have any number of edges. – bof Nov 27 '16 at 23:44
• Loop free as in there is no loop on a single vertex (counts for 2 in deg) – lucyb Nov 27 '16 at 23:52
• In that case here is a counterexample: take $3$ vertices $u,v,w$ and draw a million edges from $u$ to $v$. This is a disconnected loop-free graph. – bof Nov 27 '16 at 23:55

## 2 Answers

Suppose, to the contrary, that $G$ is disconnected. Then $G$ has at least two components. It suffices to prove the claim for when $G$ has exactly two components, $C_1$ and $C_2$ (think about why).

Suppose $|V(C_1)|=i$ and $|V(C_2)|=n-i$. The number of edges in $C_1$ is at most $\binom{i}{2}=\frac{i(i-1)}{2}$ (the number of edges in a complete graph with $i$ vertices), and the number of edges in $C_2$ is at most $\binom{n-i}{2}=\frac{(n-i)(n-i-1)}{2}$.

All you need to prove now is that for $1 \leq i \leq n-1$ $$\frac{i(i-1)}{2}+ \frac{(n-i)(n-i-1)}{2} \leq \frac{(n-1)(n-2)}{2}.$$

• thanks but shouldn't there be a + 1 on the right hand side? – lucyb Nov 28 '16 at 0:10
• @lucyb You need to find the $i$ that gives you equality in that inequality, which means that a disconnected graph can have $(n-1)(n-2)/2$ edges. This would show that a graph must then have $(n-1)(n-2)/2 + 1$ edges. Hope that helps! – Sarah Nov 28 '16 at 0:15
• that helps, thanks! – lucyb Nov 28 '16 at 0:30

Hint. Suppose $G$ is a disconnected $n$-vertex graph. Then $G$ has a connected component with $r$ vertices for some $r$ with $1\le r\le n-1.$ Thus $G$ is a subgraph of the disconnected $n$-vertex graph $K_r+K_{n-r}$ which has $\binom r2+\binom {n-r}2$ edges. Now, what values of $r\in\{1,\dots,n-1\}$ maximize this number?