How to check whether a graph is connected in polynomial time?

I have to solve the following problem:


Consider the problem Connected:


Input: An unweighted, undirected graph $G$.


Output: True if and only if $G$ is connected.


Show that Connected can be decided in polynomial time.

I have been at this for hours, and I can't seem to find a way to prove this.
Any hints?

Besides the usual deterministic DFS/BFS approaches, one could also consider a randomized algorithm. I will shortly describe a randomized algorithm for deciding if two vertices $s$ and $t$ are connected. It can also be used to decide if the whole graph is connected. The main benefit is that this method requires $O(\log |V|)$ bits of space, whereas a BFS/DFS requires $\Omega(|V|)$ space.

The cover time of an undirected graph $G=(V,E)$ is the maximum over all vertices $v \in V(G)$ of the expected time to visit all of the nodes in the graph by a random walk starting from $v$. Using some theory of Markov chains, it is not too hard to prove the cover time of $G$ if bounded from above by $4|V|\cdot|E|$.

The algorithm for deciding if $s$ and $t$ are connected is simple:

Input: two vertices s,t
1. Start a random walk from s.
2. If t is reached within 4|V|^3 steps, return true. Otherwise, return false.

Clearly, if there is no path between $s$ and $t$ the algorithm returns the correct answer. If there is a path, the algorithm errs if it is not found within $4|V|^3$ steps. The cover time of $G$ is bounded from above by $4|V||E| < 2|V|^3$. Using Markov's inequality, the probability that a random walk takes more than $4|V|^3$ steps to reach $t$ from $s$ is at most $1/2$. In other words, the algorithm returns the correct answer with probability $1/2$, and only errs by saying $s$ and $t$ are not connected when they in fact are.

StackExchange Computer Science Q#11177, answer score: 4