EDITED to include c.
Could someone help me understand this problem? I haven't been able to comprehend what I am supposed to do here.
1) Let G be a graph without self loops and parallel edges with n vertices and m edges. Consider the following procedure:
a) $G' \leftarrow G$
b) While there is a vertex of degree stricly less than $m/n$ do:
c) Remove this vertex and all its edges from the graph, and assign to G` the new graph.
d) Recompute the degrees (note that $M$ and $n$ are fixed)
2) Return $G'$
Honestly, I feel like I should be doing derivatives in Calculus after reading this. (If that's what I'm actually supposed to do I may break my computer).
Thank you to anyone for your help.
Best Answer
We consider $G := K_{5} \cup P_{3}$. There are $12$ edges and $8$ vertices. So we remove any vertex with degree less than $\dfrac{3}{2}$. So we begin by looking at the vertices of $G$. The endpoints of $P_{3}$ each have degree $1$. And so we remove an endpoint. Now $G^{\prime} = K_{5} \cup P_{2}$. Both endpoints of $P_{2}$ have degree $1$, so we remove an endpoint, and we are left with $G^{\prime} = K_{5} \cup \{v_{6}\}$. As $v_{6}$ has degree $0$, we remove it, and so we are done, leaving $K_{5}$ as the graph.
Note: You mentioned "d) Recompute the degrees (note that M and n are fixed)". And so I did not update the ratio $\dfrac{3}{2}$ on each iteration.
Does this explain the algorithm better?