1. Yes, anything that has constant input could be done in . Howether if the coordinates have size more than 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 if your representation is an edge list, 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 if you have the adjacency matrix.
3. You can do it in , 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 (complete graph on 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 operations, so no.

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.

I hope this is helpful to anybody having trouble understanding computational time complexity for Breadth First Search a.k.a BFS.

Queue graphTraversal.add(firstVertex);

// This while loop will run V times, where V is total number of vertices in graph.
while(graphTraversal.isEmpty == false)

    currentVertex = graphTraversal.getVertex();

    // This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex.
    while(currentVertex.hasAdjacentVertices)
        graphTraversal.add(adjacentVertex);

    graphTraversal.remove(currentVertex);

Time complexity is as follows:

V * (O(1) + O(Eaj) + O(1))
V + V * Eaj + V
2V + E(total number of edges in graph)
V + E

I have tried to simplify the code and complexity computation but still if you have any questions let me know.