I was given this exercise today as homework as I'm studying Graph Theory as a subject in university and I don't really know how to solve it.Here's the full exercise:
Let $G = (V, E)$ be a graph with $n$ vertices and $m$ edges. Consider the following algorithm:
$G_0 \leftarrow G$
while $\exists u \in V(G_0)$ such that $d_{G_0}(u) < \frac{m}{n}$ do
$G_0 \leftarrow G_0\backslash\{u\}$;
return $G_0$
(a) Determine a time complexity of an efficient implemenation of the above algorithm.
(b) Prove that the returned graph, $G_0$ , cannot be a null graph.
(c) Show that any given graph contains a path of length > $\frac{m}{n}$.
I think the idea behind b) might be that if you have a graph with one vertex and no edges, said vertex wouldn't be deleted by the algorithm above, but I'm not sure this one idea counts as proof..
As for a) the time complexity surely can't be more than n-1 as I said above, there'll always be at least one vertex left(or so I think) but that's for the algorithm presented above, not a more efficient implementation
Regarding a) - the number of iterations is indeed $O(n)$, but to argue that it's the overall time complexity you must show how to find the $u$ in each iteration in $O(1)$ time.
Your proof idea for b) seems correct.
For c) - I'll give you 2 hints:
1. the value $\frac{m}{n}$ only increases
2. for any graph $G$, if $\delta(G) \ge 2$ then there exists a cycle in $G$ of length $\ge \delta(G)+1$
Good luck! :)