Given a graph with 100 vertices and 99 edges. Can you say, for sure,
that the graph is disconnected or connected? What about the case when
a graph has 100 vertices and 75 edges? What about the case when the
graph has 100 vertices and 1000 edges? Justify all your answers.

Hi, math01-ga:

For a graph with 100 vertices and 99 edges, you cannot say for sure
whether or not it is connected.

An example of how such a graph can be connected is to put 100 points
along a straightline, placing 99 edges between the pairs of "adjacent"
points.

But an example of such a graph which is not connected can be obtained
by connecting 99 vertices in a simple closed polygon (that requires 99
edges) and leaving the 100th vertex all by itself.

Now a graph with 100 vertices and only 75 edges cannot be connected. 
The general theorem here is that a connected graph on N vertices must
have at least N-1 edges.  [Proof: Consider that every connected graph
has a minimum spanning tree, necessarily of exactly N vertices and N-1
edges contained in the original graph.]  Here 75 edges is insufficient
to connect 100 vertices.

Finally, what about the case of 100 vertices and 1000 edges?  Well, it
is possible to "force" connectivity upon a graph by specifying a large
number of edges (dependent upon the number of vertices), but 1000
edges is not enough to do this for the case of 100 vertices.  Consider
for example an extension of the earlier example, in which we placed 99
vertices in a simple closed polygon (roughly in a circle), leaving the
100th vertex by itself.  We can continue adding edges to the component
with 99 vertices (without connecting to the 100th) until we have the
"complete graph" on 99 vertices and the isolated 100th vertex
remaining.  The number of edges in a complete graph on n vertices
(which we often denote K(n) or K_n) is n(n-1)/2, i.e. every pair of
distinct vertices has an edge.  Since K(99) would then have 99*98/2 =
4851 edges, without being connected, we see that it is also possible
for a graph to have 100 vertices and 1000 edges without being
connected (by taking any subset of 1000 edges in the example just
constructed).

Here's a question for the interested reader:  Given that a graph has n
vertices and m edges, what is the smallest value of m for any
particular n that will guarantee the graph is connected?

regards, mathtalk-ga

Hi,

Following your well detailed explanation, that will be:
m = ((n-1)(n-2)/2) + 1
That is, assuming a complete graph with n-1 nodes and then adding just
one more edge to connect the nth node.

Best
Hany