Graph connectedness algorithm idea Assume we are given a list of edges of a graph.  For instance in edge i we are given node numbers a(i) and b(i), being the starting and ending points respectively.  I need to write an algorithm to decide whether or not this graph is connected.  
I write down a few cases but then I find out a few more counterexamples and I don't think this is getting anywhere. Can anyone offer some help?
 A: First, as @JMoravitz pointed out, a list of edges might not give you all the necessary information, in particular there might be isolated vertices. In the following I assume that this not the case (i.e. each vertex has at least one incident edge).
A basic, but inefficient approach would be:


*

*iterate over the list of edges,

*for an edge $(x,y)$ change every occurence of $x$ and $y$ into $z$, where $z=\min(x,y)$,

*the graph is connected if and only if there is at most one distinct number left.


This can be greatly improved using the disjoint set data structure (sometimes called find-union):


*

*create (hash) tables $p : V \to V$ and $r : V \to \mathbb{N}$,

*for every vertex $v$ set $p[v]:=v$ and $r[v]:=0$,

*for every edge $(x,y)$ do $\mathtt{union}(x,y)$,

*for every vertex $v$ do $\mathtt{fupdate}\big(v,\mathtt{find}(v)\big)$,

*the graph is connected if and only if there is at most one distinct vertex among the values of $p$

*where
\begin{align}
\mathtt{find}(v) &= \mathtt{if}\ t[v]=v\ \mathtt{then}\ v\ \mathtt{else}\ \mathtt{find}(t[v])\\
\mathtt{fupdate}(v,v') &= \mathtt{if}\ v \neq v'\ \mathtt{then}\ u:=t[v],\ t[v]:=v',\ \mathtt{fupdate}(u,v')\ \mathtt{else}\ v'\\
\mathtt{union}(u,v) &= \\
& u':=\mathtt{fupdate}\big(u, \mathtt{find}(u)\big),\\
& v':=\mathtt{fupdate}\big(v, \mathtt{find}(v)\big),\\
&\mathtt{if}\ u'\neq v' \land r[u'] < r[v']\ \mathtt{then}\ p[u']:=v',\\
&\mathtt{if}\ u'\neq v' \land r[u'] > r[v']\ \mathtt{then}\ p[v']:=u',\\
&\mathtt{if}\ u'\neq v' \land r[u'] = r[v']\ \mathtt{then}\ p[u']:=v',\  r[v']:=r[v']+1\\
\end{align}


This approach can be improved even further by constructing a graph and using DFS or any other graph traversal, but this is already covered by @mapierce271's answer.
I hope this helps $\ddot\smile$
A: I think the most straightforward method would be this:
Iterate over your list of edges and count the number of distinct nodes.
Then traverse your graph (depth-first or breadth-first), again counting the number of distinct nodes. If you count the same number of nodes each time, the graph is connected.
