[hermanschaaf]

Here is another one I thought of the other day.

Q: Given V (the number of vertices), E (the number of edges) and L (a list of the edges) for a connected undirected graph, determine whether the graph is a tree.

----

A: It can be done in O(1) by: return V == E + 1

The number of vertices in a tree is always one more than the number of edges. We also know that the graph is connected, so it has to be a tree.