In order to assert that a given algorithm for graphs runs in polynomial time, must the variable in the big-O function that represents the run time (denoted henceforth as $O(f(n))$) be the number of vertices? Or can one say that a graph algorithm runs in polynomial time if the variable $n$ is something else (like the number of edges in a graph).
Edit: Could an algorithm that is $O(N)$ (where $N$ is the number of trees in the graph) also be considered as being in $P$?
Informally: An algorithm is polynomial time if the algorithm runs in time polynomial in the size of the input. Suppose the input for an algorithm is a graph $G$. Then letting $n$ be the number of vertices and $m$ the number of edges, if the algorithm runs in time polynomial in either $n$ or $m$, then that algorithm is considered a polynomial-time algorithm, since the size of $G$ is $n+m$.
An algorithm that runs in time say linear in the number of trees $G$ has [which may be exponential in the size of $G$] is not in $P$. Why? The graph $G$ itself encodes all the information needed for the algorithm and so could be the input. So the algorithm would not run in time polynomial in the size of $G$.