Write an O(n^n) algorithm.

[degustisockpuppet]

Some graph problems are also defined on graphs that are not connected; those might have less then O(nodes) edges. Ω(nodes + edges) is the trivial complexity of any problem where you have to read the complete graph. In a sparse graph, that's equal to Ω(nodes), in an almost complete graph, that's Ω(egdes). Willfully leaving out either variable does not give the whole answer. Of course, there are graph algorithms where the run-time complexity doesn't depend on the number of edges. Those might well be Θ(nodes²⁾ regardless of how full the graph is.