Why isn't the Charikar algorithm for finding the densest subgraph optimal? I read about the algorithm in
Greedy Approximation Algorithms for Finding
Dense Components in a Graph by
Moses Charikar,
and I tried to find an instance/graph where the algorithm returns a different solution from the optimal one but I didn't succeed.
Can anyone provide me an example where the algorithm 'fails' and proves that the approximation is no less than 2?
Suppose you have a complete graph on four nodes and then next to it a graph with five nodes comprising a degree four hub and four degree 3 satellites. The greedy algorithm might start by removing one of the satellites and thus spoil the optimum which is 1.6

o-------o    o-------o
| \   / |    | \   / |
|   X   |    |   o   |
| /   \ |    | /   \ |
o-------o    o-------o

For the sake of completeness: given a graph $G=(V,E)$ the task is to find a subset $S\subseteq V$ maximising the quantity $|E(S)| / |S|$ where $E(S)\subseteq E$ is the set of edges with endpoints in $S$. The greedy algorithm operates by successively removing vertices of minimal degree and then searching for the optimal $S$ among the successively shrinking set of remaining vertices.