These are basically two different perspectives or two different ways of viewing the running time. Both are valid (neither is incorrect), but is arguably more useful in the settings that typically arise in AI.

In the algorithms community and CS theory community, folks there tend to like to count the running time as a function of the number of vertices and edges in the graph. Why? In that context, worst-case running time is what makes most sense; also, in the problems that are typically considered in that community, in the worst case we need to examine the entire graph, so you typically can't hope to do better than .

In the AI community, folks tend to count the running time differently. They often consider a specific kind of graph: a tree with branching factor . Also, in the situations that arise there, the graph is often infinite or very large. Typically we try hard to avoid examining all of the graph -- that's often one of the major goals of the algorithms. Thus, counting complexity in terms of and doesn't make sense: may be infinite, and in any case, we don't plan on examining all of the graph, so all that matters is the number of vertices we actually visit, not the number that may exist elsewhere but that we don't care about.

So, for the situations that often arise in the AI community, it's often more meaningful to measure the running time in terms of the branching factor of the tree () and the depth of the goal node (). Typically, once we find the goal node, the algorithm stops. In such a tree, if we examine every vertex at depth before we find the goal node, we'll end up visiting vertices before we stop. Thus, if you like, you could think of this as visiting a subset of the graph with (where now includes only the vertices we visit) and ( includes only the edges we look at), and you could think of an -time algorithm as one whose running time is ... though this is a bit of an abuse of the notation. Anyway, hopefully you can see why is more informative than in this context.

In practice, graphs often have more edges than vertices. Consider the case where this is not true: A graph where |E| < |V|. Such a graph can be, for instance, a simple path where the vertices are connected to each other in a chain. And in such cases, you might ask yourself whether this structure even needs to be represented as a graph.

In more complex graphs, you will find more edges than vertices. On the other extreme, a fully connected graph has O(|V|^2) edges. For such graphs, you are comparing an O(|V|^4) algorithm with an O(|V|^5) algorithm.

So, although it is not true for ALL graphs, those graphs that you might encounter in practice will benefit more from an O(|V|^2|E|) algorithm than an O(|E|^2|V|) algorithm.

1. Yes, anything that has constant input could be done in $O(1)$. Howether if the coordinates have size more than $O(1)$ than you will not be able to even read them in time.
2. That depends on your representation of the graph and what operations do you count. If you assume that you read the whole graph in some way and then find the needed degree, the complexity will be $O(|V| + |E|)$ if your representation is an edge list, $O(|V|^2)$ if it is an adjacency matrix. If you assume that you already have some representation of the graph in memory you can find the degree in $O(|V|)$ if you have the adjacency matrix.
3. You can do it in $O(|V| + |E|)$, start with an empty graph (all the degrees are zero) and add the edges one by one. When you add an edge to the graph only two vertices change their degrees.
4. No, consider the graph $K_4$ (complete graph on $4$ vertices). All the degrees in it are odd so it does not have even en Euler path.
5. If you want to read the coordinates it takes $O(n)$ operations, so no.

What time complexity is this?

Without sharing your data or algorithm, it's hard to say anything for sure, but based on the picture alone it looks like O(n²) to me.

Your graph plots the function S(n) = T(n) / n and the tops of the peaks look roughly co-linear, so I'm going to assume that S(n) is O(n). Then T(n) = n * S(n) = n * O(n) = O(n^2).