Graph Theory - Show that if G is simple and |E(G)| (n-1)(n-2)/2, then G is connected.

My first attempt was by induction on the number of vertices (n). I wanted to show that the graph with n+1 vertices was the complete graph Kn with an extra vertex, and since |E(G)| was strictly bigger than Kn, then there had to be a edge connecting Kn and it's extra vertex.

Am I off? Is there another way you would do it?

Thanks.

Question

Graph Theory - Show that if G is simple and |E(G)| > (n-1)(n-2)/2, then G is connected.

My first attempt was  by induction on the number of vertices (n). I wanted to show that the graph with n+1 vertices was the complete graph Kn with an extra vertex, and since |E(G)| was strictly bigger than Kn, then there had to be a edge connecting Kn and it's extra vertex.

Am I off? Is there another way you would do it?

Thanks.

anonymous · Answer

Ack, I see an issue with supposing that I'd get Kn. But if it wasn't that way, wouldn't it already be connected?

kinggeorge · Answer

A complete graph has $${n(n-1) \over 2}$$vertices correct?

anonymous · Answer

yes

kinggeorge · Answer

I would then prove this by induction. Start with a base case or two of $n=1, 2$ and maybe even $n=3$ (just for kicks). Assume it's true for some $k<n$ and then we need to show for $k+1$.

anonymous · Answer

So the real work comes in when I try to show that the | E(G) | > (n+1-1)(n+1-2)/2 = n(n-1) /2.

It'd have to have at least one more edge than Kn but with one extra vertex. So by the pigeonhole principle, it would have to be connected to some vertex in Kn, and therefore G would be connected.

Something like that?

kinggeorge · Answer

Take your graph that's simple, and has more edges than $(n-1)(n-2)/2$. 

Now add another vertex. This means we want to show that if G is simple and $$|E(G)| > {k(k-1) \over 2}$$( I got this by just substituting $k+1$ into $(n-1)(n-2)/2$)

Now we have $k+1$ vertices. Of the first $k$ that we drew, let's make that into the complete graph $K_k$. Notice that this must have exactly $k(k-1)/2$ edges. 

Now, to make sure we have more than this amount of edges, we have to add one more edge. However, since the first part of our graph is complete, and the total graph must be simple, this edge must connect to the point we just added. Therefore it's connected.

What you said is just what I tried to formalize a bit here.

anonymous · Answer

Thanks. For the induction hypothesis I just supposed it worked up to k+1 vertices.

so then I could use that |E(G)| > k(k-1)/2. Since G has more edges than the complete graph Kn and one more vertex u, there must exist an edge between Kn and the vertex u.

kinggeorge · Answer

That sounds like a good way to do it.