One way to think about connectivity is that on every cut in the graph, there should be at least one edge crossing that cut (otherwise, there is no way from a vertex on one side of the cut to the other side).

Consider a set S of some fixed size m ≤= n/2. What's the chance the cut defined by S has no edges across it? Can you show that with high probability (with c large enough), there is no cut without any edges across it?