Question $5.($Densest Subgraph$)(20$ pts$).$ Consider the graph G represented in Figure $2..$ Recall the greedy algorithm for computing a dense subgraph: at each step one node with minimum degree is removed; at the end we output the subgraph $H=(V_H,E_H)$ with maximum density $=|E_H\frac{|}{|}{V}_H|$ among all considered subgraphs.

a$)(6$pts$)$ Run the greedy algorithm on $G$ and report the subgraph computed by such an algorithm. If there are two nodes with the same degree, you should remove the one with a smaller index. E$.$g$.$ between $8$ and $9$ you should remove $8.$

b$)(6$pts$)$ What is the densest subgraph in $G($i$.$e$.$ it maximizes $|E{H}_H\frac{|}{|}V{H}_H|)?$

c$)(8$pts$)$ Change the first node to be removed so that greedy computes a densest subgraph. You can only choose the first node to be deleted, the rest of the algorithm is unchanged. This applies only in the case when the densest subgraph was not found already in a$).$