How to better prove this statement? Let G be a graph with $n$ vertices and $k > {n-1 \choose 2}$ edges. Then G is connected

Question

I tried doing it by contrapositive. I'm here to ask two things

1) Whether this proof is correct

2) If there's a better, more direct way of proving this using graph theory

Here's how I did it:

Let G be a non-connected graph with n vertices. Then G has at most ${n-1 \choose 2}$ edges

Proof:

If G isn't connected, it has two subgraph components F and H, such that $ \#V_F = m$ and $\#V_H = n - m$, $ 1 \le m \le n-1$

$\#E_F + \#E_H = \#E_G$ and also $\#E_F \le \#E_{K_m}$ and $\#E_H \le \#E_{K_{n-m}}$

So from this follows that $ \#E_G = \#E_F + \#E_H \le \#E_{K_m} + \#E_{K_{n-m}} = {m \choose 2 } + {n-m \choose 2}$

So I'll define $f(m) = {m \choose 2 } + {n-m \choose 2}$ and I want to prove that

$ \Delta f(m) \le 0$, for $1 \le m \le \lfloor \frac {n-1}{2} \rfloor$

$\Delta f(m) \ge 0$, for $\lceil \frac{n-1}{2} \rceil \le m \le n-1$

$f(m) = f(n-1) = {n-1 \choose 2}$

This would prove f(m) has its maximum value at m=1. And then the maximum amount of edges in G is f(1).

I'm not writing the proof for these three last statements, but it's easy to prove knowing that $\Delta f(m) = 2m+1-n$

Thanks in advance!

Answer 1

Your proof is correct, but there is a simple one using the degree sum formula.

Since twice the number of edges is the sum of the vertex degrees, the average degree is greater than $$\frac{(n-1)(n-2)}{n} > n-3$$ so there must be a vertex $v$ of degree at least $n-2$. If $v$ is of degree $n-1$ the graph is clearly connected, so suppose $v$ is of degree $n-2$, and let $x$ be the one vertex not adjacent to $v$. The subgraph induced by $v$ and its neighbors has at most $\binom{n-1}{2}$ edges, so there is an edge from $x$ to some neighbor of $v$, and the graph is connected.

Answer 2

This proof is correct, and I think most if not all other proofs are variants of this one. (Edit: saulspatz gives a proof very different from this one, which I like, so clearly that was false. I mean, not literally false, since I gave myself an out by not making an absolute statement, but maybe I was overstating my case.)

There are a couple of other, very similar ways to get to where you're going:

1. Since $f(m)$ is a convex function, it is maximized over the interval $[1,n-1]$ at one of the boundary points: $f(1)$ or $f(n-1)$. In this case, the two are equal, and both give $\binom{n-1}{2}$.
2. Alternatively, we can minimize the quantity $\binom n2 - f(m) = m(n-m)$. This has a combinatorial interpretation as well: it is the number of edges guaranteed to be missing from a graph with a connected component of size $m$.
3. Either way, instead of thinking about the discrete derivative $\Delta f(m)$, it's fine to just deal with the derivative $f'(m) = 2m-n$. This leads to a proof that $m=1$ and $m=n-1$ are not just better than all integer values $m \in \{2,3,\dots,n-2\}$ but also fractional values like $m=1.5$, but that's fine as long as we don't end up getting a fractional optimal value.

We could also put together two well-known facts: first, that if a graph is not connected, then its complement is; second, that a connected graph on $n$ vertices has at least $n-1$ edges. This lets us conclude that at least $n-1$ edges are missing from a disconnected graph, so it has at most $\binom n2 - (n-1) = \binom{n-1}{2}$ edges. But proving the first of these facts is strictly harder than proving the result we're trying to get, so this isn't really a shortcut.

Answer 3

Your proof is a valid one. As an another approach, by using the argument below, we can also go with induction:

Let $G$ be a non-connected graph with n vertices. Then $G$ has at most ${n-1 \choose 2}$ edges.

Since a graph with $1$ vertex is said to be connected, we should start from $n=2$. For $n = 2$, we can construct a disconnected graph in only one way where there are no edges, that is $\binom{2-1}{2} = 0$.

Now suppose, inductively, that the argument holds for all $n$. Then for a graph with $n+1$ vertices, if we construct this graph by adding a one vertex to a graph with $n$ vertices, in order to maximize the number of edges, obviously we should add the new vertex to the component with more vertices. Therefore, we add the new vertex to the component with $n-1$ vertices. Then connecting all other vertices to the new vertex (except the isolated vertex that provides disconnectivity), we add $n-1$ more edges to $\binom{n-1}{2}$ edges to get: $$\binom{n-1}{2}+n-1 = \frac{(n-1)(n-2)}{2}+(n-1) = \frac{n^2-n}{2} = \frac{n(n-1)}{2} = \binom{n}{2}$$ Since it holds for $n+1$, by induction, the argument holds for all $n \ge 2$.

Answer 4

A slightly different approach. If we assume that a graph on $n$ vertices is not connected, it has at least two connected components and the number of its edges is at most

$$ \max_{\substack{a+b=n\\ a,b\geq 1}}|E(K_a)|+|E(K_b)| = \max_{\substack{a+b=n\\ a,b\geq 1}}\binom{a}{2}+\binom{b}{2}=\max_{1\leq a \leq n-1}\frac{2a^2-2an-n+n^2}{2}$$ where $f(a)=2a^2-2an-n+n^2$ is a convex function. It follows that the previous maximum is attained at $a=1$ or at $a=n-1$ and a disconnected graph on $n$ vertices has at most $\binom{n-1}{2}$ edges.