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

Question

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?

Answer 1

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.

---

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.