Prove that a graph with $n$ vertices is connected if it has $(n^2 - 3n + 4)/2$ edges.

Question

Let $G$ be a graph with $n > 2$ vertices with $(n^2 − 3n + 4)/2$ edges. Prove that $G$ is connected.

This is my assignment question and I have no idea how to approach. Please suggest something.

Answer 1

An Approach

Let's think about what it would mean to be disconnected. One possibility is that there is an isolated vertex, all off on its own, not connected to anything else. Then the other $n-1$ vertices must have edges only to each other. How many edges can $n-1$ vertices fit? The complete graph on $n-1$ vertices has $(n-1)(n-2)/2 = (n^2 - 3n + 2)/2$ edges, and you have more than that.

So we see that we don't have an isolated vertex.

What about two vertices that are disconnected from the other $n-2$? Do some edge counting there. What about three?

Then the method will probably be clear.