NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

Consider the following decision problems:

$$CONN$$= {$$〈G,k〉$$$$G$$ is undirected graph with at least $$k$$ connected components}
$$E-CONN$$= {$$〈G,k〉$$$$G$$ is undirected graph with exactly $$k$$ connected components}

I'd like to show this two problem are in $$NL$$. I Know it's possible to guess a vertex from each connected component and then verify the connectivity of the component (by guessing paths to other vertices). But how can I verify all guessed vertices are different, when it's impossible to hold $$k$$ vertices on the work tape?

• Hint: Use NL = coNL. – dkaeae Jun 11 at 9:35
• Hint: As you've observed, you cannot hold $k$ guesses at once. Instead, go through every vertex and maintain some counter. – sdcvvc Jun 11 at 9:39

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 < v_2 < \cdots < 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.