# Algorithm for finding a specific ordering of nodes in a graph $G=(V, E)$ in $O(|V|+|E|)$ time

I have an undirected graph $$G=(V,E)$$ and I want to find an ordering of $$V$$, $$\pi=(v_1, v_2, ..., v_n)$$, such that for each $$1 \leq i \leq n$$, $$v_i$$ is of minimum degree in the subgraph $$G_i = [\{v_1, ..., v_{i-1}, v_i\}]_G$$ in $$O(n+m)$$ time, where $$n=|V|$$ and $$m=|E|$$. I also have to prove that if $$G$$ is a tree, then a greedy coloring algorithm that colors the nodes in the order they are found in $$\pi$$ will always use at most 2 colors.

My idea was to first compute the degree of each node in the graph (which can be done in $$O(m)$$), store the values in an array, then sort that array in descending order using an $$O(n)$$ sorting algorithm like Counting Sort or Radix Sort. However, it seems this approach isn't entirely correct, as I found a counterexample for which the coloring algorithm has to use 3 colors. So if this isn't the way to go about it, how can I find $$\pi$$ in $$O(n+m)$$?

• Is this a homework problem? Dec 22 '21 at 7:07
• Hint: Vertex with the minimum degree in $G$ is the last vertex in the ordering. Do this process inductively. Dec 22 '21 at 7:08