NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}
We can assume without loss of generality that the vertex set is $1,\ldots,n$.
Let us say that a vertex is minimal if it has the minimal value in its connected component. You can check that a vertex in minimal in NL by checking that it is not connected to any smaller vertex.

A graph has at least $k$ connected components iff there is a list $v_1 &lt; v_2 &lt; \cdots &lt; v_k$ of minimal vertices. This shows that CONN is in NL. Since NL=coNL, it follows that E-CONN is also in NL.

Morale: if you want to make sure that you guessed $k$ distinct vertices, guess them in increasing order.



Since undirected connectivity is in L, we can actually count the number of connected components in L, by just going over all vertices, and counting how many of them are minimal.