Nev0:

D>>Критерий дерева: количество рёбер на 1 меньше количества вершин.
> Небольшая поправка: причем граф должен оставаться связным.

Да, Вы правы — я поспешил.
Добавлю. Связность проверяется поиском в ширину/глубину, как подсказал
mkopachev.