Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$ Let $G=(V,E)$ be a graph.
Let $m(G)=|E|$ and $n(G)=|V|$.
There are two different density definitions for $G$:
$$d_1(G)=\frac{m(G)}{n(G)}$$
and
$$d_2(G)=\frac{m(G)}{n(G)-1}.$$
Let $H^* \subseteq G$ be a subgraph of $G$ such that
$$d_1 (H^*)\geq d_1 (H)$$
for any subgraph $H\subseteq G$.
My question is:
Is it true that for any subgraph $H\subseteq G$ we still have
$$d_2 (H^*)\geq d_2 (H)?$$
Any comment is welcome!
Update 1:
J.G showed that the statement is NOT TRUE by providing a counterexample.

Consider two disjoint triangles connected by a single edge. Without checking too formally, $^*$ is the full graph with value $7/6$ under the first definition, but either of the triangles has value $3/2$ under the second definition while the full graph only has value $7/5$.

Update 2:
I found that a maximum density subgraph (with the definition $d_1(G)=\frac{m(G)}{n(G)}$) can be found efficiently by using algorithms provided in references:

A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, University of California at Berkeley, 1984.
G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A Fast Parametric Maximum Flow Algorithm and Applications. SIAM Journal on Computing, 18(1):30–55, 1989.

However, I didn't find any reference for computing a maximum density subgraph (with the definition $d_2 (G)=\frac{m(G)}{n(G)-1}$).
As pointed by J.G, a maximum $d_1$-density subgraph may not be a maximum $d_2$-density subgraph.
My new question is:
Is there any efficient algorithm for computing a maximum density subgraph (with the definition $d_2 (G)=\frac{m(G)}{n(G)-1}$)?
Here is a very slow algorithm, but it handles more general cases, like when density is defined as $d_\beta(G) = \frac{m(G)}{n(G)-\beta}$.
Let $f$ be a submodular function, $g$ be a modular function strictly larger than $0$. The min ratio problem $\min_S f(S)/g(S)$ can be solved in polynomial time. Indeed, use the standard to convert min ratio problem to parametric search problem with linear terms.
Consider we have input graph $G=(V,E)$.
For $d_\beta$ density, fix a set $T$ of size $k = \lfloor \beta \rfloor + 1$, and define $f_T:2^{V-T} \to \mathbb{R}$ as $f_T(S) = -m(G[T\cup S])$, and define $g_T:2^{V-T} \to \mathbb{R}_{&gt;0}$ as $g_T(S) = |S|+|T|$. You can check $f$ is submodular through a counting argument.
Consider the optimum $T$ and $S$ for $$\min_{T:|T|=k, T\subset V} \min_{S:S\subset V\setminus T} f_T(S)/g_T(S).$$ Let $T$ and $S$ be the optimum of the problem. The densest subgraph is $G[T\cup S]$.
Running time is $O(n^k)$ calls to the min ratio oracle. Maybe faster algorithm exists, be nice to avoid that $k$ in the exponent.